Manual Do Prof Yuri
Manual Do Prof Yuri
Manual Do Prof Yuri
FACULDADE DE CIÊNCIAS
DEPARTAMENTO DE MATEMÁTICA E INFORMÁTICA
Maputo, 2019
Introdução
Lógica, ou, mais exactamente, Lógica Matemática é um ramo da Matemática que estuda
os princípios e métodos para distinguir proposições válidas e das não válidas, os princípios e
métodos das demonstrações e questões dos fundamentos da matemática.
A Teoria de Conjuntos um ramo da Matemática que estuda as propriedades gerais dos
conjuntos de elementos de qualquer natureza que tenham qualquer tipo de propriedade co-
mum. Estudam-se operações básicos entre conjuntos, relações e funções, na forma mais geral,
independentemente das operações e propriedades algébricas ou geométricas entre elementos dos
conjuntos.
Os princípios básicos da Lógica e da teoria das demonstrações, sem dúvida, englobam todas
as areas da Matemática, tais como Álgebra, Análise, Geometria, Matemática Discreta e etc.
De outro lado, nas todas as áreas da Matemática, estudam-se os objectos matemáticos, que,
em primeiro lugar, estão os conjuntos, e em segundo, são dotados das operações e propriedades
adicionais (algébricas, geométricas e etc.).
Sendo assim, o conhecimento da disciplina tem muita importância para especialistas de todas
as especialidades do DMI.
O presente manual é preparado na base do manual do Prof. Doutor Sergei Labovskiy :
[1] Sergey Labovskiy, Introdução a lógica e teoria de conjuntos, Maputo, DMI, 2010.
Também foi signicativamente utilizado o manual do Prof. Doutor Nguyen Cong Hoan :
[2] Nguyen Cong Hoan, Lógica e Teoria de Conjuntos, lições para os cursos Estatística,
Informática e Matemática, Maputo, DMI, 2013.
Em particular, o Capitulo IV e inteiramente retirado de [2].
Nas várias perguntas nos usamos também manuais, textos de apoio, exercícios e testes do
Prof. Doutor Vladimir Bessonov e Prof. Doutor Alexandre Kalashnikov.
Agradeço ao Professor Doutor Andrey Shindyapin e aos Mestres Tome Eduardo Sicuaio e
Stefane Draiva Saize pelas observações e o melhoramento do texto!
I Lógica 4
1 Proposições 5
1.1 Proposições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Negação (¬) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Conectivos disjunção (∨) e conjunção (∧) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Equivalência das proposições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5 Conectivos condicional (→) e bicondicional (↔) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6 Fórmulas proposicionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.7 Tautologia. Contradição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.8 Implicação. Equivalência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.9 Leis de álgebra de lógica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.10 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Predicados 17
3.1 Predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2 Quanticador universal (∀) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 Conceitos de implicação e de equivalência generalizados . . . . . . . . . . . . . . . . . . . . . . . 17
3.4 Quanticador existencial (∃) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.5 Variáveis livres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.6 Leis de Morgan: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.7 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 Teoremas e demonstrações 21
4.1 Estrutura do teorema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Teoremas recíproco, contrário e contra-recíproco . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.3 Métodos de demonstração directos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3.1 Demonstração de ∀x P (x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3.2 Demonstração de P ⇒ Q. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3.3 Teoremas na forma de equivalência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.3.4 Vários casos na premissa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.4 Métodos de demonstração indirectos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.4.1 Uso do teorema contra-recíproco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.4.2 Redução ao absurdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.4.3 Exclusão de variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.5 Dedução (raciocínio dedutivo) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.6 Teoremas e linguagem matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.7 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1
5 Demonstração de validade de argumento 29
5.1 Argumento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 Demonstração formal de validade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3 Demonstrações de validade directa e indirecta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.4 Exemplos de demonstrações de validade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
5.5 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
6 Indução matemática 35
6.1 Introdução. Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.2 Princípio da indução matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
6.3 Princípio de indução generalizado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.4 O princípio fraco de indução matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.5 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
II Conjuntos 39
7 Conceito de conjunto. Operações sobre conjuntos 40
7.1 Conceito de conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.2 Métodos de representação de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.2.1 Lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.2.2 Propriedade característica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
7.3 Conjuntos numéricos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.4 Conjuntos nitos e innitos. Conjuntos equivalentes . . . . . . . . . . . . . . . . . . . . . . . . . 41
7.5 Inclusão. Conjunto universal. Conjunto de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.5.1 Inclusão (⊂) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.5.2 Conjunto universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.5.3 Conjunto de conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.5.4 Diferença dos sentidos de ∈ e ⊂ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.6 Operações sobre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.6.1 Complemento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
7.6.2 União e intersecção (∪ e ∩) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7.6.3 Diferença e diferença simétrica (r e 4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7.6.4 Diagramas de Venn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
7.7 Lógica e teoria de conjuntos sobre conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.7.1 Denição das operações sobre conjuntos usando conectivos . . . . . . . . . . . . . . . . . 44
7.7.2 Relação entre conjuntos e predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
7.8 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2
11 Funções 60
11.1 Denição de função . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
11.2 Composição de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
11.3 Funções injectivas, sobrejectivas, bijectivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
11.4 Funções inversas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
11.5 Imagem e pré-imagem de conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
11.6 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
11.6.1 Exercícios (secção 11.1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
11.6.2 Exercícios (secções 11.2-11.4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
11.6.3 Exercícios (secção 11.5) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3
Tema I
Lógica
4
Capítulo 1
Proposições
5
2. Sejam O símbolo de equivalência de duas proposições usa-se
⇔ ou ≡. Como uma generalização do exemplo acima
A = {Vai chover}, B = {Vamos a praia} temos a equivalência das proposições
P Q P ∧Q P ∨Q
1.5 Conectivos condicional (→) e
F F F F bicondicional (↔)
F V F V
V F F V Para criar fórmulas proposicionais usam-se mais dois
V V V V conectivos → e ↔ que são determinados por meio da
tabela de verdade
pode ser formulada: não é verdade que não vai cho- O conectivo → diz-se condicional. O resultado da fór-
ver e vamos à praia. Representando usando conectivos mula A → B é verdade se no caso A for verdade, a
vamos ter proposição B logo deve ter o valor verdade. O con-
¬Q = ¬(¬C ∧ P ). teúdo da formula A → B pode ser descrito também
pela uma das seguintes frases:
Então, ¬Q é verdadeira se pelo menos uma das pro- − se A é verdadeira, então B é verdadeira
posições ¬A ou B é falsa, isto é se uma das negações (mais brevemente, se A, então B )
¬¬A ou ¬B é verdadeira, ou é verdadeira a proposição − de A segue B ;
− B quando A;
C ∨ ¬P. − para que B seja verdadeira é suciente que A seja
verdadeira
O resultado podemos representar assim (mais brevemente, para B é suciente A);
− para que A seja verdadeira é necessário que B
¬(¬C ∧ P ) é equivalente a C ∨ ¬P. seja verdadeira
(mais brevemente, para A é necessário B ).
Então, a negação agora pode ser formulada: O conectivo ↔ diz-se bicondicional. O conteúdo da
formula A ↔ B pode ser descrito pela uma das seguin-
Vai chover ou não vamos à praia.
tes frases:
− A é verdadeira se e somente se B é verdadeira
Como uma generalização do exemplo acima temos a
(mais curto, A sse B );
equivalência das proposições
− A quando e só quando B ;
¬(A ∧ B) ⇔ ¬A ∨ ¬B. − para A é necessário e suciente B ;
Vamos pensar sobre a frase: de A segue B e ao
O exemplo apresentado mostre a importância da se- mesmo tempo de B segue A. É claro isto signica que
guinte denição. A sse B é verdade (independentemente dos valores de
verdade de A e B ). Isto signica que das proposições
Denição 1.1. Duas proposições P e Q dizem-se equi- (A → B) ∧ (B → A) e A ⇔ B são equivalentes:
valentes se têm as mesmas colunas na tabela da ver-
dade. (A → B) ∧ (B → A) ⇔ A ⇔ B.
6
Recomendamos demonstrar esta equivalência usando a Observamos também, que nos denimos conectivos
tabela de verdade. → e ↔ directamente pela tabela de verdade. Mas nos
Exemplo 1.2. Analisar as frases: vários manuais, como em [2], estes conectivos são de-
nidos por meio das proposições equivalentes. Assim,
1. Se não vai chover, então vamos à praia. se escrever de maneira curta, em [2] é colocado, pela
denição,
2. Vamos à praia sse não vai chover.
def.
Análise: Sejam p → q ⇔ ¬(p ∧ ¬q),
def.
C = {Vai chover} e P = {Vamos à praia}. p ↔ q ⇔ (p → q) ∧ (q → p)
1. A primeira proposição pode ser representada: É claro que neste caso as tabelas de verdade para → e
↔ são mesmas que acima, só não como denições, mas
¬C → P. como resultados obtidos das equivalências acima. De
outro lado, usando a denição pela tabela, temos as fór-
Observamos que se C é falsa (abbr., F), i.é. se não mulas da denição alternativa usar leis da Álgebra de
vai chover), então ¬C → P é verdadeira (abbr. Lógica. Para entender melhor de que se trata, apresen-
V) somente quando P é V (exactamente vamos tamos uma analogia geométrica simples. O quadrado
passar à praia). Mas se C é V, i.e. vai chover, pode ser denido como um losango com todos os ângu-
então da frase não implica nada sobre passagem los rectos, e também como um rectângulo com todos os
para a praia. Portanto, se C é V, então ¬C → P lados iguais. O resultado é a mesma gura geométrica.
é V, independentemente do valor de verdade da
proposição P .
Este raciocínio da lógica habituada ou intuitiva
1.6 Fórmulas proposicionais
está em conformidade com a denição do conectivo Usando conectivos podemos construir novas proposi-
→ para o que vemos com a ajuda da tabela de ções a partir das variáveis proposicionais. Por exem-
verdade plo,
C P ¬C ¬C → P P = (A ∨ ¬B) ∧ C
F F V F é uma proposição representada por meio da fórmula
F V V V com as variáveis proposicionais A, B , C . Vamos dizer
V F F V P é proposição composta ou fórmula proposicional que
V V F V depende das variáveis proposicionais A, B e C . Pode-se
escrever P = P (A, B, C).
2. A segunda proposição pode ser representada: A tabela de verdade para a formula proposicional P
é
P ↔ ¬C. A B C ¬B A ∨ ¬B E
F F F V V F
Observamos que esta proposição é verdadeira,
F F V V V V
quando P é V (vamos a praia) e C é falsa (não
F V F F F F
vai chover), ou quando P é F (não vamos a praia)
F V V F F F
e C é V (vai chover).
V F F V V F
Este raciocínio da lógica habituada ou intuitiva V F V V V V
está em conformidade com a denição do conectivo V V F F V F
↔ para o que vemos com a ajuda da tabela de V V V F V V
verdade
Nos usamos na tabela acima a ordem dos valores de ver-
C P ¬C P ↔ ¬C dade para variáveis proposicionais A, B , C começando
F F V F de F, como no manual [1], mas pode-se usar ordem co-
F V V V meçando de V, como no manual [2]. Às vezes o valor
V F F V de verdade V designa-se por 1 e o valor de verdade F
V V F F designa-se por 0:
7
1.7 Tautologia. Contradição B) ⇔ ¬A ∨ ¬B . De facto, da tabela de verdade
8
principais. Nas leis p, q, r, s signicam proposições ar- 13. Leis de Condicional 1
bitrárias e T, C a tautologia e a contradição, respecti-
vamente. p → q ⇔ ¬p ∨ q
p → q ⇔ ¬(p ∧ ¬q)
1. Lei de Adição
p ⇒ p∨q
14. Lei de Bicondicional
2. Leis de Simplicação p ↔ q ⇔ (p → q) ∧ (q → p)
9
1.10 Exercícios (f) f → (2 · 2 = 5), F
(g) g ↔ (2 · 2 = 5), V
Os exercícios 16, 8 são da cha do doutor Bessonov:
(h) h ↔ (2 < 3), V
1. Indique as frases que são proposições:
(i) i ↔ (2 > 3), V
(a) A cidade de Paris é a capital de Moçambique (j) j ↔ (2 < 3), F
(b) Um quadrilátero é um losango (k) k ↔ (2 > 3), F
(c) A área de superfície da esfera do raio R é (l) se 4 é numero par então l, V
igual a 4πR2
(m) se m, então 4 é numero par, V
(d) Todos os triângulos são semelhantes
(n) se 4 é numero par então n, F
(e) Todo homem tem dois lhos
(o) se p, então 4 é numero par, F
(f) x2 + 2x + 1 = 0
6. Determine se for possível o valor de verdade das
(g) 33 − 3 · 10 + 3 ≥ 0
expressões seguintes (seja λ(P ) o valor de verdade
(h) A = {0, 1, 3, 5} da P )
2. Formule negações para as proposições seguintes: (a) (a → b) → c, λ(c) = 1,
(a) O rio Zambeze banha a cidade de Maputo (b) a ∧ (b → c), λ(b → c) = 0,
(b) 36 é divisível por 6 (c) a ∨ (b → c), λ(b) = 0,
(c) 4 > −1 (d) ¬(a ∨ b) ↔ (¬a → ¬b), λ(a) = 1,
(d) 6 ≤ 2 (e) (a ∧ b) → (a ∨ c), λ(a) = 0.
3. Indique quais das proposições em pares seguintes 7. Determine os valores de verdade das variáveis pro-
são negações uma da outra (explique, porquê): posicionais Pi sabendo os valores de verdade das
proposições compostas Gi :
(a) 5 > 1 e 5 < 1
Proposição Valor de verdade
(b) 3 ≤ 5 e 3 > 5
G1 ≡ (P1 ∧ (3 > 1)) ∨ ¬P1 Verdadeiro
(c) {Todos os números primos são pares} e {To-
G2 ≡ ¬P2 ↔ (23 = 5) Falso
dos os números primos são impares}
G3 ≡ P3 → (¬P3 ∨ (5 ≤ 3)) Falso
(d) {Todos os números primos são impares} e G4 ≡ (¬P4 ∧ (3 ≤ 3)) → P4 Verdadeiro
{Existe um número primo que é par} G5 ≡ (P5 ∧ (1 < 5)) ↔ ¬P5 Verdadeiro
(e) {Existem números irracionais} e {Todos os G6 ≡ (¬P6 → (1 > 5)) ∨ P6 Falso
números são racionais} G7 ≡ (P7 → (2 > 3)) ∧ ¬P7 Verdadeiro
G8 ≡ P8 → (¬P8 ∨ (2 < 3)) Falso
4. Determine os valores de verdade das proposições G9 ≡ (¬P9 → P9 )) ∨ ¬P9 Verdadeiro
seguintes:
Apresente os resultados na tabela por sinal ×.
(a) 7 é um número primo e 9 é um número primo
(b) 7 é um número primo ou 9 é um número só V só F V ou F nenhum
primo P1
(c) 2 · 2 = 4 e 2 · 2 ≤ 5 e 2 · 2 ≥ 4 P2
P3
(d) Se 12 é divisível por 6 então 12 é divisível por
P4
3
P5
(e) Se 11 é divisível por 6 então 11 é divisível por P6
3 P7
(f) 12 é divisível por 6 sse 12 é divisível por 3 P8
P9
5. Determine os valores de verdade das variáveis pro-
posicionais a, b, . . . , sabendo o valor de verdade Respostas: Designando as colunas da tabela a par-
das proposições a seguir: tir de "só V" por 1,2,3,4 obtemos as respostas:
(a) a ∧ (2 · 2 = 4), V 3,2,1,1,4,2,2,4,3.
(b) b ∧ (2 · 2 = 4), F 8. Construía as tabelas de verdade para as expressões
(c) c ∨ (2 · 2 = 5), V dadas:
(d) d ∨ (2 · 2 = 5), F (a) P ∧ ¬Q
(e) e ∧ (2 · 2 = 5), F (b) ¬(P → Q)
10
(c) P → (Q ∨ R) (g) Se vou tomar muito vinho, então não vou en-
(d) (P → Q) ∨ (P → R) tender lógica nem álgebra (V,L,A).
10. Analise as proposições usando uma forma simbó- C = {a Neide tiver credito}
lica (Exercícios na pagina 8 (Cong, Lógica e Teoria T = {vai telefonar para amigas}
de Conjuntos)): M = {vai mandar mensagens}
(a) Não ocorre que eu seja seu amigo (A) A primeira ideia
(b) Se ela é uma gata, então ela tem quatro per-
nas (G,P) (C → T ) ∧ (¬C → M ),
(c) O preço do arroz aumenta se e somente se o mas esta solução não é certa. De facto, se
suprimento de arroz não atende à demanda a Neide não tem credito, então não pode te-
(P,S) lefonar e neste caso se C é F e T e M são
(d) Ou os grandes laboratórios reduzem os preços é V a fórmula tem que ter o valor F. Mas a
ou o governo intervirá (L,G) substituição directa destes valores da verdade
das variáveis proposicionais à fórmula escrita
(e) Se a exportação de carne aumentar ou se a
dá-nos a vol de verdade V! Por isso, é cor-
produção pecuária decair, então o custo de
recto descrever a situação por meio da uma
vida subirá (E, P, C)
das fórmulas:
11. No Domingo um estudante decidiu resolver a ta- (C → T ) ∧ (¬C → (¬T ∧ M )) ou
refa de Álgebra, ir ao cinema, visitar um museu e, (C → T ) ∧ (¬C → ¬T ) ∧ (T ∨ M ) ou
também, se não chover, ir jogar futebol na praia. (C ↔ T ) ∧ (T ∨ M )
Em que caso podemos dizer que o programa do
estudante não foi realizado? Resolver o problema Os estudantes podem vericar a equivalência
sem usar as fórmulas de lógica, mas depois, com das fórmulas usando a tabela de verdade.
as formulas. (b) O Hélio foi convidado para passar todo o Sá-
bado na casa do tio que vive longe. Se o Hélio
12. Seja dada a proposição P . acordar cedo, vai apanhar o transporte e vai
1) Escreva a proposição P na forma simbólica passar o Sábado com seu tio, mas se o Hé-
usando os símbolos sugeridos. lio acordar tarde, vai perder o transporte e
2) Escreva a negação da proposição P na forma vai aproveitar o dia para cortar o cabelo e
simbólica e simplique até a forma que contém estudar Lógica.
negações só antes das variáveis proposicionais.
3) Escreva a negação da proposição P em palavras (c) A Célia vai cozinhar caril de cabrito e fazer
(sem símbolos). uma sobremesa, que, se houver ovos, vai ser
um bolo, mas se não houver, vai ser gelatina.
Considere as seguintes variantes de P :
11
Capítulo 2
12
Solução: Exemplo 2.4. Demonstrar a lei de exportação
P ∨ (Q ∧ ¬P ) (p ∧ q) → r ⇔ p → (q → r)
⇔ (P ∨ Q) ∧ (P ∨ ¬P ) (lei distributiva)
⇔ (P ∨ Q) ∧ T (lei de complemento) usando o raciocínio dedutivo.
⇔ P ∨Q (lei de identidade) Resolução: 10 método.
p → (q → r)
Observamos que a regra acima tem uma analogia
⇔ p → ¬(q ∧ ¬r) (lei de condicional 1)
intuitiva com a 2a lei transitiva 16 e pode ser escrita
⇔ ¬(p ∧ ¬¬(q ∧ ¬r)) (lei de condicional 1)
na forma:
⇔ ¬(p ∧ (q ∧ ¬r)) (negação dupla)
⇔ ¬((p ∧ q) ∧ ¬r) (lei associativa)
(F1 ⇔ F2 ) ∧ (F2 ⇔ F3 ) ` (F1 ⇔ F3 ) (2.1)
⇔ (p ∧ q) → r (lei de condicional 1)
O símbolo ` signica implica logicamente ou deduz- Observamos, que da lei comutativa para conectivo bi-
se e chama-se símbolo de dedução. De facto, é quase condicional segue que as leis F1 ⇔ F2 e F2 ⇔ F1 são
mesma lei 16, mas só usada no outro nível: em vez equivalentes, então é possível considerar com sendo a
de conectivo condicional ↔, torna-se uma equivalência mesma lei. Então, na demonstração nos deduzimos da
⇔, e em vez de implicação ⇒, torna-se uma dedução `. proposição da parte direita da lei de exportação à pro-
A expressão (2.1) serve como método de resolução do posição na parte esquerda.
seguinte problema: a partir da fórmula F1 e por meio 20 método.
de duas equivalências lógicas deduzir a fórmula F3 que
é equivalente à fórmula inicial F1 . p → (q → r)
A formula (2.1) pode ser generalizada para: ⇔ p → (¬q ∨ r) (lei de condicional 1)
⇔ ¬p ∨ (¬q ∨ r) (lei de condicional 1)
(F1 ⇔ F2 ) ∧ (F2 ⇔ F3 ) ∧ . . . ∧ (Fn−1 ⇔ Fn ) ⇔ (¬p ∨ ¬q) ∨ r (lei associativa)
` (F1 ⇔ Fn ). ⇔ ¬((p ∧ q) ∨ r) (lei de Morgan)
⇔ (p ∧ q) → r (lei de condicional 1)
O método de demonstração correspondente pode ser
apresentado no esquema: 2.3 Raciocínio dedutivo para im-
F1 plicações
⇔ F2 (justicação)
⇔ F3 (justicação) Para demonstrar leis da Álgebra de Lógica na forma
··· de uma implicação lógica F1 ⇒ F2 é possível usar o ra-
⇔ Fn (justicação) ciocínio dedutivo, que é análogo ao raciocínio dedutivo
para equivalências.
onde justicação signica o uso de uma ou várias leis É claro, que se são válidas duas implicações F1 ⇒ F2
de Álgebra de Lógica. e F2 ⇒ F3 , então, segundo 1a lei transitiva, é válida
O método de demonstração da equivalência lógica de também a implicação F1 ⇒ F3 . Simbolicamente, te-
duas fórmulas proposicionais F1 e Fn descrito chama-se mos
método de dedução ou raciocínio dedutivo (veja [H]).
(F1 ⇒ F2 ) ∧ (F2 ⇒ F3 ) ` (F1 ⇒ F3 ) (2.2)
De facto, a simplicação da fórmula no Exemplo 2.3
é realizada pelo método de raciocínio dedutivo. De facto, é quase mesma lei 16, mas só usada, no nível
Uma aplicação importante do método de raciocínio mais alto, analogamente à fórmula (2.1). A fórmula
dedutivo é a demonstração das leis de Álgebra de Ló- (2.2) serve como raciocínio dedutivo para o seguinte
gica a partir das outras leis, já conhecidas. problema: a partir da fórmula F1 e por meio das duas
Então temos dois métodos de transformação das fór- implicações lógicas deduzir a fórmula F3 , para obter a
mulas proposicionais e de demonstração das Regras de implicação F1 ⇒ F3 .
Inuência: A formula (2.2) pode ser generalizada para:
1) o método usando a tabela de verdade;
2) o método do raciocínio dedutivo. (F1 ⇒ F2 ) ∧ (F2 ⇒ F3 ) ∧ . . . ∧ (Fn−1 ⇒ Fn )
(2.3)
O método usando a tabela de verdade é melhor para ` (F1 ⇒ Fn ).
fórmulas simples. Por exemplo, a lei p ∧ T ⇔ p é
A demonstração de uma implicação lógica F1 ⇒ Fn do
facilmente demonstra-se por meio da tabela de verdade.
método de raciocínio dedutivo pode ser apresentada
Ao contrário, o método de raciocínio dedutivo mais
pela esquema:
úteis para fórmulas e para leis complicadas. Se, por
exemplo, queriam demonstrar uma lei "nova" contendo F1
5 variáveis proposicionais e 10 conectivas, o número dos ⇒ F2 (justicação)
símbolos V e F da tabela de verdade é 25 · 10 = 320! ⇒ F3 (justicação) (2.4)
É claro que neste caso é mais racional usar raciocínio ···
dedutivo. ⇒ Fn (justicação).
13
É claro que este raciocínio será correcto, se em vez de Desta tabela podemos concluir que os valores V na
algumas implicações ⇒ cam equivalências ⇔. tabela de uma FND correspondem aos termos que
Exemplo 2.5. Demonstrar a lei de silogismo disjuntivo são conjunções elementares. Por exemplo, o primeiro
termo
(p ∨ q) ∧ ¬p ⇒ q a ∧ ¬b ∧ c
é verdadeiro sse a tem o valor V , b tem o valor F , c
usando o raciocínio dedutivo.
tem o valor V .
Resolução:
Então, para obter uma FND a partir da tabela de
(p ∨ q) ∧ ¬p verdade, podemos usar o segundo algoritmo:
⇔ ¬p ∧ (p ∨ q) ( lei comutativa) 1. Consideremos todas as linhas que possuem V na
⇔ (¬p ∧ p) ∨ (¬p ∧ q) ( lei distributiva) última coluna;
⇔ C ∨ (¬p ∧ q) (leis comut. e de compl.) 2. Construímos para cada uma destas linhas as conjun-
⇔ (¬p ∧ q) ∨ C (lei comutativa) ções elementares correspondentes: tomamos xi = ai
⇔ ¬p ∧ q (lei de identidade) para todas ai Verdadeiras e xi = ¬ai para todas ai
⇒ q (lei de simplicação) Falsas (veja a tabela abaixo);
3. Escrevemos a disjunção destas conjunções elemen-
Então, a lei (p ∨ q) ∧ ¬p ⇒ q é demonstrada. tares.
a b c F1
F F F F
2.4 Formas normais disjuntiva e F F V V ¬a ∧ ¬b ∧ c
conjuntiva F V F F
F V V F
Sejam a, b, c variáveis proposicionais. As expressões V F F F
V F V V a ∧ ¬b ∧ c
a ∧ b ∧ c, ¬a ∧ b ∧ ¬c, a ∧ ¬b ∧ c, . . . V V F F
V V V V a∧b∧c
vamos chamar conjunções elementares. Consideremos
uma denição em geral. Então (segundo ponto 3),
Denição 2.2. Uma disjunção C1 ∨ C2 ∨ · · · ∨ Ck diz- é falso sse a tem o valor F , b tem o valor V , c tem o
se forma normal disjuntiva (ou FND) se C1 , C2 , . . . Ck valor F .
são conjunções elementares diferentes. Então, para obter uma FNC a partir da tabela de
verdade, podemos usar o segundo algoritmo:
Por exemplo, 1. Consideremos todas as linhas que possuem F na
última coluna;
F1 = (a ∧ ¬b ∧ c) ∨ (¬a ∧ ¬b ∧ c) ∨ (a ∧ b ∧ c)
2. Construímos para cada uma destas linhas as disjun-
é uma forma normal disjuntiva. ções correspondentes: tomamos xi = ai para todas ai
Analogamente pode ser considerada uma forma nor- Falsas e xi = ¬ai para todas ai Verdadeiras (veja a
mal conjuntiva (FNC) que é uma conjunção de disjun- tabela abaixo);
ções elementares, por exemplo 3. Escrevemos a conjunção destas disjunções.
F2 = (a ∨ ¬b ∨ c) ∧ (¬a ∨ ¬b ∨ c) ∧ (a ∨ b ∨ c). a b c F2
F F F F a∨b∨c
Consideremos as tabelas de verdade para F1 e F2 : F F V V
F V F F a ∨ ¬b ∨ c
a b c F1 F2 F V V V
F F F F F V F F V
F F V V V V F V V
F V F F F V V F F ¬a ∨ ¬b ∨ c
F V V F V V V V V
V F F F V
V F V V V Então (segundo ponto 3),
V V F F F
V V V V V F2 = (a ∨ b ∨ c) ∧ (a ∨ ¬b ∨ c) ∧ (¬a ∨ ¬b ∨ c).
14
Teorema 2.1. Cada fórmula proposicional tem as for- concepção do manual não permite fazer isto):
mas FND e FNC equivalentes à mesma.
x y z p para FND para FNC
Então, podemos concluir que cada fórmula do cál- F F F V ¬x ∧ ¬y ∧ ¬z
culo proposicional pode ser representada por meio das F F V V ¬x ∧ ¬y ∧ z
operações de negação, conjunção e disjunção. F V F V ¬x ∧ y ∧ ¬z
De facto, dos algoritmos apresentados segue a res- F V V V ¬x ∧ y ∧ z
posta positiva do Problema de Post (Emil Leon Post, V F F F ¬x ∨ y ∨ z
18881995), veja [2]. Apresentemos esta resposta na V F V F ¬x ∨ y ∨ ¬z
forma seguinte: V V F V x ∧ y ∧ ¬z
V V V F ¬x ∨ ¬y ∨ ¬z
Teorema 2.2 (Post). Para cada proposição composta
(que depende de um número nito das variáveis pro- Então, a FND de p é:
posicionais livres) denida por tabela de verdade existe
uma fórmula proposicional que a determina. (¬x ∧ ¬y ∧ ¬z) ∨ (¬x ∧ ¬y ∧ z)∨
(¬x ∧ y ∧ ¬z) ∨ (¬x ∧ y ∧ z) ∨ (x ∧ y ∧ ¬z).
Observamos também, que para cada fórmula propo-
sicional a FND equivalente é determinada unicamente, A FNC de p é:
ao menos a ordem das conjunções elementares e a or-
dem das variáveis proposicionais na cada conjunção ele- (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ ¬z).
mentar. Analogamente, para FNC.
Finalmente, notemos, que para Contradição que de- Observação. É possível achar a FND e FNC de p
pende de n variáveis proposicionais, o número k das também por raciocínio dedutivo, mas como regra, para
conjunções elementares na FND C1 ∨ . . . ∨ Ck é zero, as FND e FNC este método é pior (mais complicado)
tal que coloquemos, pela denição, que a FND de C do que o método de uso a tabela de verdade.
é a mesma C . Analogamente, pela denição, a FNC
Exemplo 2.7. Ache as tabelas de verdade para as se-
para uma Tautologia T é mesma T .
guinte fórmulas proposicionais:
Como exemplos, apresentemos as FND e FNC para
T e C no caso de duas variáveis proposicionais x e y : a) F1 = (a ∧ b ∧ ¬c) ∨ (a ∧ ¬b ∧ c) ∨ (¬a ∧ c),
15
A tabela de verdade da fórmula F1 é 2.6 Exercícios
a b c F1 1. Usando as leis de álgebra de proposições ache uma
F F F F fórmula equivalente que contém negações aplica-
F F V V das só às variáveis proposicionais (do método de
F V F F raciocínio dedutivo):
F V V V
(a) ¬((x ∧ y) ∨ ¬z)
V F F F
V F V V (b) x ∧ ((x ∧ y) ∨ ¬(y ∧ z) ∨ ¬(y ∨ (¬t ∧ z)))
V V F V (c) ¬(x → y)
V V V F 2. Usando o raciocínio dedutivo simplique as se-
guintes fórmulas:
A proposição F1 é V , quando uma das conjunções ele-
mentares é V . A primeira conjunção elementar a∧b∧¬c (a) ¬(¬a ∨ b) → ((a → ¬b) → a)
é Verdadeira se as variáveis livres a, b e c têm valores (b) ¬(¬a ∧ ¬b) ∨ ((a → b) ∧ a)
de verdade V , V e F , respectivamente (sétima de 8 (c) (a → b) ∧ (b → a) ∨ (a ∨ b)
linhas). Analogamente consideram-se três outras con-
junções elementares. (d) (a → b) ∧ (b → ¬a) ∧ (c → a)
20 método. Construímos a tabela directamente da (e) (a ∧ c) ∨ (a ∧ ¬c) ∨ (b ∧ c) ∨ (¬a ∧ b ∧ c)
forma de F1 usando a sua representação na forma de (f) ¬((a → b) ∧ (b → ¬a))
disjunção de três conjunções (seja a última conjunção
3. Transforme cada uma das fórmulas seguintes para
não é elementar).
uma forma que só tem operações de negação e dis-
A primeira conjunção a ∧ b ∧ ¬c é verdadeira sse a,
junção:
b e c são V, V e F, respectivamente (sétima linha da
tabela). (a) (x → y) → (y ∧ z)
A segunda conjunção a ∧ ¬b ∧ c é verdadeira sse a, (b) (¬x ∧ ¬y) → (x ∧ y)
b e c são V, F e V, respectivamente (sexta linha da (c) ((¬x ∧ ¬y) ∨ z) → (z ∧ ¬y)
tabela).
A terceira conjunção ¬a ∧ c é verdadeira sse a e c são 4. Ache a negação de cada uma das seguintes fór-
F e V, respectivamente, mas b é qualquer (segunda e mulas e apresente na forma que contém negações
quarta linhas da tabela). aplicadas só às variáveis proposicionais:
Então obtemos a mesma tabela que que foi obtida (a) (x ∧ (y ∨ ¬z)) ∨ (¬x ∧ y)
do 10 método.
(b) ((¬x ∧ ¬y ∧ ¬z) ∨ r) ∧ ¬f ∧ ¬u ∧ ¬w
b) A fórmula F2 já tem a FNC. A tabela de verdade
é: (c) (((¬x ∧ (¬y ∨ z)) ∨ p) ∧ ¬q) ∨ (¬r ∧ (s ∨ ¬t))
(d) (x ∧ (¬y ∨ (¬z ∧ p)) ∨ ¬q) ∧ r
x y z t F2 5. Para cada uma das fórmulas seguintes ache as
F F F F V FND e FNC:
F F F V V
F F V F V (a) ¬(¬x ∨ y) → ¬z
F F V V V (b) ¬(y → z) ∧ (x ∨ z)
F V F F V (c) (¬x ∧ y) → ¬(x → z)
F V F V F
(d) (x → y) → z
F V V F V
F V V V V (e) (x ∧ ¬z) → (x ↔ y)
V F F F F (f) ((x → y) → (z → ¬x)) → (¬y → ¬z)
V F F V V (g) (x ↔ y) ∧ ¬(z → t)
V F V F V (h) (x ∨ (y ∧ ¬z)) ∧ (x ∨ z)
V F V V V
V V F F V 6. Para cada uma das seguintes proposições, apre-
V V F V V sente a tabela de verdade, constituída apenas das
V V V F V colunas de variáveis proposicionais e da proposi-
V V V V V ção resultante (sem o uso das colunas auxiliares
para as sub-fórmulas):
Notemos que dois valores Falsos estão nas linhas que
correspondem as disjunções elementares Falsas. A pri- (a) (¬x ∨ y ∨ ¬z) ∧ (y ∨ z)
meira disjunção elementar x ∨ ¬y ∨ z ∨ ¬t é Falsa se as (b) x ∨ (x ∧ ¬y ∧ z)
variáveis livres x, y , z e t têm valores de verdade F , V , (c) (x∧¬y∧z)∨(¬x∧¬y∧z)∨(¬x∧y∧z)∨(x∧y)
F e V , respectivamente. Analogamente considera-se a (d) (x∨¬y∨z)∧(¬x∨¬y∨z)∧(¬x∨y∨z)∧(x∨y)
segunda disjunção elementar. Nas outras 16 − 2 = 14
(e) x ∧ ¬y ∧ z ∧ ¬t ∧ ¬s
linhas o valor de verdade de F2 é V .
16
Capítulo 3
Predicados
17
A implicação por exemplo, P (1, 5, 2) é uma proposição F, visto que
P ⇒Q ∆ = b2 − 4ac = 17 > 0, e respectivamente a equação
x2 − 5x + 2 tem raises reais.
(P implica Q) é uma proposição denida por
Agora, consideremos a outra expressão composta (o
(∀x ∈ U ) P (x) → Q(x). conjunto universal é R):
P (a, b, c) = ∀x(ax2 + bx + c > 0). ∀x(P (x) ∧ Q(x)) ⇔ ∀xP (x) ∧ ∀xQ(x)
∃x(P (x) ∨ Q(x)) ⇔ ∃xP (x) ∨ ∃xQ(x).
Observamos que P (a, b, c) não é uma proposição com-
posta, porque as variáveis livres não são variáveis pro- A demonstração do Teorema 3.2 oferece-se aos estu-
posicionais, mas são números reais. Observamos que, dantes como um exercício.
18
Observação. A proposições (b) ∃y∀x(x < y)
(c) ∃x∀y(x < y)
∃x(P (x) ∧ Q(x)) e ∃xP (x) ∧ ∃xQ(x)
(d) ∀y∃x(x < y)
não são equivalentes, mesmo que as proposições (e) ∃x∃y(x < y)
∀x(P (x) ∨ Q(x)) e ∀xP (x) ∨ ∀xQ(x). (f) ∀x∀y(x < y)
Este facto conrma-se por meio do exemplo: o univer- 5. Analise a forma lógica das frases a seguir. O uni-
sal é o conjunto de números reais, P (x) = {x ≥ 0}, versal é R. Indique as variáveis livres.
Q(x) = {x < 0}. (a) Cada número maior do que x é maior do que
y.
3.7 Exercícios (b) Para qualquer a a equação ax2 + 4x − 2 = 0
tem pelo menos uma solução se e somente se
1. Os predicados a seguir são denidos sobre o con- a ≥ −2.
junto N de todos os números naturais: (c) Todas as soluções da inequação x3 − 3x < 3
são menores do que 10.
I(n) ≡ {n2 = n + 1}
M (n) ≡ {n > 1} (d) Se existe um número x tal que x2 + 5x = w e
existe um número y tal que 4 − y 2 = w, então
P (n) ≡ {n(n + 1) é par} w pertence ao intervalo [−10; 10].
Q(n) ≡ {n2 > 3}
6. São as proposições seguintes verdadeiras ou falsas?
O universal é N
Quais das proposições são verdadeiras? (a) ∀x∃y(2x − y = 0)
(a) ∀nI(n) (b) ∃y∀x(2x − y = 0)
(b) ∀nM (n) (c) ∀x∃y(x − 2y = 0)
(c) ∀nP (n) (d) ∀x(x < 10 → ∀y(y < x → y < 9))
(d) ∃nI(n) (e) ∃y∃x(y + x = 100)
(e) ∃nM (n) (f) ∀x∃y(y > x ∧ ∃z(y + z = 100))
(f) ∃nP (n) 7. O universal é N. Para cada uma das seguintes
(g) ∃n(M (n) ∧ P (n)) proposições:
1) Escreva a proposição em palavras e verique se
(h) ∃n(M (n) ∨ P (n))
é verdadeira ou falsa;
(i) ∀n(M (n) ∧ P (n)) 2) Escreva a negação da proposição dada na forma
(j) ∀n(M (n) ∨ P (n)) simbólica e reduza usando a lei de Morgan.
(k) ∀n(M (n) → Q(n)) (a) ∀x∃y∀z(x + y ≥ 3z)
(l) ∃n(M (n) → Q(n)) (b) ∀z∀x∃y(x + y ≥ 3z)
2. Construir as negações das proposições considera- (c) ∃x∀y∃z(x + y ≥ 3z)
das no exercício precedente usando as leis de Mor- (d) ∀y∃z∃x(x + y ≥ 3z)
gan. Analisar o resultado obtido.
(e) ∀x∃y∀z(z < y < x)
3. Analise as formas lógicas das frases: (f) ∃x∀y∃z(z < y < x)
(a) Um dos estudantes da turma não conseguiu (g) ∀y∃z∃x(z < y < x)
fazer o trabalho. (h) ∀z∀x∃y(z < y < x)
(b) Qualquer coisa neste mercado é muito cara (i) ∀x∃y∀z(x > y ∨ x > z)
ou tem defeitos
(j) ∃x∀y∃z(x > y ∨ x > z)
(c) Ninguém é perfeito
(k) ∀y∃z∃x(x > y ∨ x > z)
(d) A Laura gosta de qualquer pessoa que não
(l) ∀z∀x∃y(x > y ∨ x > z)
gosta da Maria
8. Ache as negações das seguintes proposições
4. Discute o signicado das proposições. São verda-
deiras ou falsas? O universal é o conjunto N de (a) Qualquer pessoa tem um vizinho que não
todos os números naturais. gosta de ninguém
(a) ∀x∃y(x < y) (b) ∀y > 0∃x(ax2 + bx + c = y)
19
9. São as seguintes proposições verdadeiras ou falsas? (e) Existe pelo menos uma solução da equação
O universal é N ax2 + bx + c = 0.
11. Negue as seguintes declarações e expresse o resul- ¬∃xP (x) ⇔ ∀x¬P (x)
tado em forma de uma declaração positiva:
15. Mostre que
(a) Todo aquele que é formando em matemática
tem um amigo que precisa de ajuda com a ∃x(P (x) → Q(x)) ⇔ ∀xP (x) → ∃xQ(x).
tarefa de casa
(b) ∀a∀b∀c((b2 −4ac ≥ 0) → ∃x(ax2 +bx+c = 0))
(c) ∀x(P (x) → Q(x))
(a) ∃y(x = y 2 )
(b) ∃z(x = yz)
(c) x > 1 ∧ ¬∃y∃z(x = yz ∧ y < x ∧ z < x)
20
Capítulo 4
Teoremas e demonstrações
No presente capitulo será discutido em detalhes o P (∆) e Q(∆) onde ∆ simboliza um triângulo. A propo-
que é que um Teorema e qual é a sua estrutura, serão sição P (∆) → Q(∆) é verdadeira para triângulo qual-
considerados os métodos básicos da demonstração de quer, i.e. a proposição
teoremas. A matéria é preparada na base do manual
[1]. É claro que o tema tem uma grande importância ∀∆(P (∆) → Q(∆))
para todos so ramos de Matemática. é verdadeira.
O exemplo a seguir tem a mesma estrutura lógica.
Seja n um número natural. Se n não é múltiplo de 3
4.1 Estrutura do teorema então n2 − 1 é múltiplo de 3. A premissa é
21
para que x seja múltiplo de 4 é necessário As diagonais de losango são perpendiculares,
que o último digito do x seja par.
mas o recíproco é:
O teorema A ⇒ B pode ser também escrita na forma
equivalente: a condição A é uma condição suciente Se as diagonais de um quadrilátero são per-
para B , isto é, pendiculares então o quadrilátero é losango.
para que o último digito dum número inteiro Claro que o teorema A ⇒ B é verdadeiro mas o teo-
x seja par é suciente que o x seja múltiplo rema recíproco B ⇒ A é falso.
de 4. No caso quando os teoremas A ⇒ B e B ⇒ A são
verdadeiras temos a equivalência
No entanto, no teorema presente a condição B ainda
não garante que o número x seja múltiplo de 4, isto é, A ⇔ B.
B não é condição suciente para A.
Analogamente, existem números pares para os quais De cada uma das A e B decorre a outra. Neste caso
não é válido A, isto é, A não é condição necessária para cada das condições é necessária e suciente para outra.
B. Podem ser usadas as formulações:
Notemos que omitir o quanticador ∀x na formu-
lação do teorema pode-se só sabendo o signicado e 1. Para que A seja verdadeira é necessário e suciente
importância do quanticador. Por exemplo, a proposi- a condição B ,
ção 2. A é verdadeira se e somente se é verdadeira B ,
As diagonais de paralelogramo
(4.3)
são perpendiculares e outras equivalentes.
não é verdadeira. Representemos este 'teorema' na Mais uma vez notemos que a formulação exacta tem
forma a forma
A⇒B ∀x(A(x) ↔ B(x)).
onde Se num teorema A ⇒ B substituir por suas negações,
vamos ter um teorema contrário em relação ao inicial:
A(Q) = {o quadrilátero Q é um paralelogramo}
B(Q) = {as diagonais do Q são perpendiculares}. ¬A ⇒ ¬B.
A implicação A(Q) → B(Q) não é teorema, porque é O teorema contrário ao recíproco ¬B ⇒ ¬A é contra-
um predicado com variável livre Q que pode ter valor recíproco.
verdadeiro (se Q é um losango) ou falso (se Q é um Seja A ⇒ B o teorema considerada no exemplo 4.2.
paralelogramo que diferente do losango). Mas se adici- O teorema contrário tem a forma
onar o quanticador universal, obteremos uma propo-
sição (4.3), que é falsa: Se um quadrilátero não é losango então as
diagonais de losango não são perpendiculares.
∀Q (A(Q) → B(Q)).
O teorema contra-recíproco:
Esta última proposição diz que as diagonais de qualquer
paralelogramo são perpendiculares que não é verdade. Se as diagonais de um quadrilátero não são
perpendiculares então o quadrilátero não é lo-
sango.
4.2 Teoremas recíproco, contrá-
rio e contra-recíproco Por causa das equivalência
A ⇒ B ≡ ¬B ⇒ ¬A
Seja A ⇒ B um teorema. O teorema
B⇒A o teorema contra-recíproco é verdadeiro se e somente
se o teorema inicial é verdadeiro. Nesta equivalência
diz-se reciproco em relação ao primeiro. Claro que um é baseado um dos métodos de demonstração descrito
dos teoremas (ou ambos) pode ser falso enquanto o abaixo.
outro é verdadeiro. Notemos que, analogamente, o teorema recíproco é
Notemos que o teorema recíproco tem a forma equivalente ao teorema contrário:
exacta:
∀x (B(x) → A(x)). B ⇒ A ≡ ¬A ⇒ ¬B.
Exemplo 4.2. Sejam
Exemplo 4.3. Consideremos seis teoremas:
A(Q) = {o quadrilátero Q é um losango} Teorema 1. A soma de duas funções contínuas é uma
B(Q) = {as diagonais de Q são perpendiculares}. função contínua.
Teorema 2. Se duas funções são contínuas então a
O teorema A ⇒ B signica: soma deles também é uma função contínua.
22
Teorema 3. Se as funções f e g são contínuas, então 4.3 Métodos de demonstração di-
a função f + g é contínua.
Teorema 4. Uma função representável na forma de
rectos
soma de duas funções contínuas é contínua.
Teorema 5. Se uma função é a soma de duas funções
4.3.1 Demonstração de ∀x P (x)
contínuas então essa função é contínua. Consideremos o seguinte
Teorema 6. Se h = f + g onde f e g são funções Teorema A. Para todo número natural n3 − n é múl-
contínuas, então a função h também é contínua. tiplo de 3.
Primeiro, observamos que todos os seis teoremas 1-6 Usando as designações
são equivalentes entre si e representa-se versões textu-
ais diferentes de uma teorema fundamental da Análise N (n) = {n é número natural},
Matemática. Também, é claro do contexto, que as fun- P (n) = {n3 − n é múltiplo de 3}
ções tem que ser denidos no mesmo domínio J que o teorema A pode ser escrita na forma
pode ser, por exemplo, um dos intervalos ]a, b[, [a, b],
]a, ∞[, [a, ∞[ ou R =] − ∞, ∞[. Para simplicação da ∀n (N (n) → P (n))
formulação foram omitidas as palavras em relação a
este domínio J , mas é evidente do contexto de que se Mas o mesmo teorema admite uma forma equivalente
trata.
Apesar do facto que teoremas 1-6 são equivalentes, ∀x ∈ N P (x).
as suas formalizações P ⇒ Q são diferentes! Nos teo-
remas 1-3 o objecto é um par das funções contínuas, e Se do contexto é claro que o conjunto universal é o
conclui-se que a soma deles é contínua. Mas nos teore- conjunto dos números naturais N, na forma mais curta
mas 4-6 o objecto é uma função contínua e considera-
∀x P (x)
se a sua continuidade na condição de representação na
forma de soma das funções contínuas. Mais precisa- Mesmo que no exemplo considerado, na maioria dos
mente: teoremas é preciso demonstrar a veracidade de uma
Em relação aos Teoremas 1-3, o conjunto universal proposição da forma ∀xP (x).
U é conjunto dos pares das funções (f, g) denidas num Uma demonstração pode começar com a frase:
intervalo,
Seja x um elemento arbitrário.
A(f, g) = {f e g são funções contínuas},
B(f, g) = {f + g e função contínua}. Por exemplo, demonstramos o teorema A. Podemos
raciocinar:
Os Teoremas 1-3 na forma simbólica são:
Demonstração. Seja n um número natural. Temos n3 −
∀(f, g) ∈ U (A(f, g) → B(f, g)). n = (n − 1)n(n + 1) é produto de três números inteiros
não negativos consecutivos. Um entre estes números é
O teorema recíproco aos Teoremas 1-3 é múltiplo de 3. Por isso o produto é também múltiplo
de 3.
∀(f, g) ∈ U (B(f, g) → A(f, g)),
Então, o esquema de demonstração é:
ou pelas palavras: se a soma f + g de suas funções
é contínua, então as funções f e g são contínuas. É Seja x um elemento qualquer
evidente que este teorema é Falso. Demonstrar P (x)
Em relação aos Teoremas 4-6, O conjunto universal
V é o conjunto das funções denidas num intervalo.
4.3.2 Demonstração de P ⇒ Q.
P (h) = {h = f + g onde f e g são contínuas}, A forma P ⇒ Q é realmente ∀x(P (x) → Q(x)). Vamos
Q(h) = {h é função contínua}. ter o esquema:
Isto é,
O teorema recíproco aos Teoremas 4-6 é
Sejam x um elemento qualquer e P (x)
∀h ∈ V (Q(h) → P (h)),
Demonstrar Q(x)
ou pelas palavras: qualquer função contínua é represen-
tável na forma de duas funções contínuas. É evidente Consideremos um exemplo concreto.
que este teorema é Verdadeiro. Teorema B. Se x > 2, então x2 > 4.
23
Subentende-se que deve ser demonstrado: Demonstração. Necessidade. Seja a equação x2 + 2x +
a = 0 tem raises reais. Então, o discriminate da equa-
∀x ∈ R (x > 2 → x2 > 4). ção é não-negativo, isto é ∆ ≥ 0. Calculando
24
4.3.4 Vários casos na premissa 4.4 Métodos de demonstração in-
Consideremos um teorema P ⇒ Q onde a premissa P directos
se representa a disjunção das condições P = P1 ∨P2 tal
que, pelo conteúdo, não é possível (ou é complicado) 4.4.1 Uso do teorema contra-recíproco
realizar a demonstração simultaneamente para o caso
O método é baseado sobre a equivalência
da condição P1 e para o caso P2 . Segundo a lei de
condicional 2 de Álgebra de Lógica, P ⇒ Q ≡ ¬Q ⇒ ¬P
(P1 ∨ P2 ) ⇒ Q ≡ (P1 ⇒ Q) ∧ (P2 ⇒ Q) do teorema dado e do teorema contra-recíproco. Em
vez do teorema dado pode ser demonstrado o teorema
Então, para demonstrar o teorema (P1 ∨ P2 ) ⇒ Q é é contra-recíproco de um dos métodos directos descritos
suciente demonstrar cada uma das implicações na secção precedente. Apresentemos um exemplo.
P1 ⇒ Q e P2 ⇒ Q Teorema E. Se x2 ≥ x, então x ≥ 1 ou x ≤ 0.
Observamos que
Mais geral, para demonstrar um teorema P ⇒ Q no
qual ¬(x ≥ 1 ∨ x ≤ 0) ⇔ 0 < x < 1,
P = P1 ∨ P2 ∨ . . . ∨ Pn ¬(x2 ≥ x) ⇔ x2 < x.
é suciente demonstrar cada uma das implicações: O teorema contra-recíproca do teorema E é: se 0 <
x < 1, então x2 < x. A demonstração deste contra-
P1 ⇒ Q,
recíproco é mais fácil do que a demonstração directa
P2 ⇒ Q,
do teorema E. Então, a demonstração do teorema E
...
pode ser apresentado na seguinte forma:
Pn ⇒ Q.
Demonstração. É suciente demonstrar
Consideremos um exemplo concreto.
Teorema D. Demonstrar que |x+1| ≤ |x|+1 qualquer 0 < x < 1 → x2 < x.
que seja o número real x.
Seja 0 < x < 1. Multiplicando esta desigualdade por x
Temos P (x) ⇔ P1 (x) ∨ P2 (x) ∨ P3 (x) onde (que é positivo!) vamos ter 0 < x2 < x.
25
Demonstração. Sejam x + a = 10 e a > 12. Então, Q.
Suponhamos que a desigualdade x < −2 não é vá- O esquema deste método para n = 3 é:
lido, isto é x ≥ −2. Das desigualdades a > 12 e x ≥ −2
segue P, Q1 ∨ Q2 ∨ Q3 ⇔ T, P ⇒ ¬Q1
(4.6)
a + x > 12 − 2 = 10 Q2 ∨ Q3
o que contradiz a condição x + a = 10.
Consideremos um exemplo.
Contradição obtida implica x < −2.
Teorema H. Se n não é múltiplo de 3, então n2 − 1 é
Teorema G. O conjunto P de números primos é in- múltiplo de 3.
nito.
Demonstração. Método de redução ao absurdo. Supo- Demonstração. Seja n um número natural que não é
nhamos que P é nito. Apresentamos P na forma da múltiplo de 3. Entre os três números n − 1, n, n + 1 um
lista é múltiplo de 3. Mas n não é. Daqui um dos números
P = {n1 , n2 , . . . , nk } n − 1 ou n + 1 é múltiplo de 3. Então, o produto
(n − 1)(n + 1) também é múltiplo de 3. Observando
Então, o número
que n2 − 1 = (n − 1)(n + 1) concluímos que o teorema
m = n1 n2 · . . . · nk está demonstrado.
é múltiplo de cada dos números do conjunto P . Por- De facto, a demonstração apresentado foi realizada
tanto, m + 1 não é múltiplo de nenhum número primo, através do método de exclusão de variantes. Para ana-
e, respectivamente, é primo. De outro lado, m + 1 lisar isto, introduzimos o predicado
é maior do que cada elemento de P , então não pode
ser primo. Contradição obtida implica que P é in- Q(n) = {n é múltiplo de 3}.
nito.
Claro que
26
Observamos que de facto nos demonstramos o teo- Um Corolário é uma asserção que segue de um Te-
rema mais forte do que o teorema I, isto é, a equivalên- orema (ou de uma Proposição), é logicamente ligado
cia das proposições P → (Q → R) e ¬R → (P → ¬Q). com este Teorema e pode ser deduzido do teorema di-
Na prática, a dedução na demonstração dos teoremas rectamente, ou por meio do raciocínio não tão compli-
pode ser realizada não obrigatoriamente do método for- cado, como a demonstração do mesmo Teorema.
mal, mas do método misto, usando frases simbólicos e A palavra Propriedade usa-se, como regra, junto com
raciocínio de palavras. Esta forma, as vezes, é mais objecto matemático para que aplicado "Propriedade do
confortável, porque pode esclarecer os passos da forma objecto matemático A". Por exemplo, no tema "Fun-
simbólica. Assim, apresentemos a demonstração do te- ções continuas" de Análise Matemática o título Pro-
orema I nesta forma, que essencialmente, é semelhante priedade 2.1.5 signica um teorema (no sentido geral)
a segunda demonstração. que se representa uma o várias propriedades das fun-
ções contínuas.
Demonstração. Seja P → (Q → R). É preciso de-
monstrar ¬R → (P → ¬Q).
Seja ¬R. É suciente demonstrar P → ¬Q. Mas 4.7 Exercícios
para isso raciocinamos: seja P . Agora o objectivo é
demonstrar ¬Q. Então, temos a esquema 1. Forme a premissa e a conclusão e represente na
forma A ⇒ B os teoremas:
P → (Q → R), ¬R, P
(4.8) (a) As diagonais de paralelogramo dividem-se no
Demonstrar ¬Q ponto de intersecção em partes congruentes.
Das proposições P → (Q → R) e P deduzimos, pelo (b) Para quaisquer positivos a e b
lei de Modus Ponens, a proposição Q → R.
Agora, da veracidade das proposições Q → R e ¬R ln(ab) = ln a + ln b.
segue, pela lei de Modos Tollens, a proposição ¬Q.
(c) Cada número inteiro que termina por dois ze-
Observamos que na seguinte secção o teorema I será ros é divisível por 4.
considerado como um argumento, e será realizado o
método formal de demonstração de validade deste ar- 2. Indique qual das duas armações decorre da outra.
gumento. Formule o teorema usando os termos é necessário
que e os termos é suciente que (duas variantes):
27
(a) Se cada parcela é múltipla de 11, então e a (p) Pelo menos dois ângulos dum triângulo isos-
soma é múltipla de 11. celes são congruentes.
(b) Se nenhuma parcela é múltipla de 11, então (q) Se uma proposição p é falsa, então a propo-
e a soma não é múltipla de 11. sição p → q é verdadeira.
(c) Se pelo menos uma parcela é múltipla de 11, (r) Para quaisquer proposições p e q , se p ∨ q é
então e a soma é múltipla de 11. falsa, então p é falsa.
(d) Se a soma é múltipla de 11, então cada par- 7. Demonstre o teorema usando três métodos: um
cela é múltipla de 11. dos métodos directos, o método de uso do teorema
(e) Se a soma não é múltipla de 11, então ne- contra-recíproco e o método da dedução de uma
nhuma parcela é múltipla de 11. contradição (redução ao absurdo). Que método é
mais conveniente?
(f) Se a soma não é múltipla de 11, então pelo
menos uma parcela não é múltipla de 11. (a) Se x2 − 2x > 0, então x < 0 ou x > 2.
6. Para os 'teoremas' seguintes: (b) Se x2 > 4, então |x| > 2.
1) Destaque a premissa, conclusão e o conjunto, (c) Se (x − 1)(x − 3) < 0, então 1 < x < 3.
onde as são denidas. (d) Se x2 − x = 6, então x 6= 1.
2) Formule o teorema usando o termo é necessário
que. Também, formule o teorema usando o termo (e) Se x2 − x = 6, então x < 5.
é suciente que. (f) Seja 2x + y > 0. Se x < −3, então y > 6.
3) Formule três teoremas: o teorema reciproco, (g) Seja xy = x2 + y 2 . Então, x 6= 0 implica
o teorema contrário e o teorema contra-reciproco y 6= 0.
para o teorema dado.
4) Quais dos quatro teoremas (dado, recíproco, (h) Seja xy = x2 + y 2 . Então, x = 0 implica
contrário e contra-recíproco) são verdadeiros, y = 0.
quais são falsos. (i) Suponhamos que x + y = 2x − 3y . Se x e y
não são zeros simultaneamente, então y 6= 0.
(a) Se x > y e z < y , então z < x.
(j) Se x2 6= x3 , então x 6= 1.
(b) Se um triângulo é equilátero, então pelo me-
nos um dos seus ângulos internos mede 600 . 8. Seja
√
x um número real e x 6= 0. Demonstre que se
3 x+5
x +6 = x , então x 6= 8.
1
(c) A soma de ângulos internos de qualquer tri- 2
28
Capítulo 5
29
não obrigatoriamente todas! É conveniente, em cada (R ∨ B) → ¬D e D que estão nas linhas 3 e 4, res-
passo concreto, marcar os números das linhas anterio- pectivamente, implica ¬(R ∨ B), pela lei Modus Tol-
res (incluindo linhas das hipóteses) cujas proposições lens (lei 24 no parágrafo 1.7 acima). Realmente, os
são usadas para dedução de Fi e também a lei de Ál- papeis das proposições p e q na lei de Modus Tollens
gebra de Lógica usado para dedução de Fi . Então, a (p → q) ∧ ¬q ⇒ ¬p desempenham R ∨ B e ¬D, respec-
demonstração de validade para um argumento, é con- tivamente.
ciso expressar pelo seguinte esquema:
(Hip.)
1.
2.
H1
H2 (Hip.) 5.3 Demonstrações de validade
... directa e indirecta
n. Hn ` P (Hip. ` Conclusão)
(5.3)
n + 1. F1 (linhas; lei) A demonstração de validade de um argumento pelo es-
n + 2. F2 (linhas; lei) quema (5.3) denomina-se demonstração de validade di-
... recta. Realmente, é método directo de demonstração
n + m. P (linhas, lei) de um teorema (veja a Secção 4.3).
Então, listamos as hipóteses Hi e as proposições de- No entanto, na demonstração de validade de um ar-
duzidas Fi em uma coluna com a justicação de cada gumento pode ser usado o método de dedução de uma
passo numa coluna ao lado. Para fácil inuência, é contradição, baseado na lei de redução ao absurdo
conveniente enumerar as hipóteses e colocar a conclu-
são P à direita da última hipótese, separada desta por p → q ⇔ (p ∧ ¬q) → C
sinal de dedução ` que indica que todas as proposi-
ções acima e uma à esquerda são hipóteses. Abaixo que foi discutido na Secção 4.4.1.
da linha com conclusão estão linhas com proposições A demonstração de validade por redução ao absurdo
deduzidas consecutivamente das proposições que cam chama-se demonstração de validade indirecta. Um es-
acima (excepto a conclusão). Na justicação (linhas; quema formal da demonstração de validade indirecta
lei) de cada uma destas linhas escrevemos os números é:
das linhas onde estão as proposições usadas para de-
dução da proposição na linha actual e a lei de Álgebra
de Lógica usada nesta dedução. Na última linha está 1. H1 (Hip.)
a proposição que é conclusão. 2. H2 (Hip.)
...
Denição 5.1. Uma demonstração formal de validade n. Hn ` P (Hip. ` Conclusão)
de um argumento é uma sequência das proposições n + 1. ¬P (Demonstração Indirecta)
cada uma das quais é ou uma hipótese do argumento n + 2. P1 (linhas; lei)
ou segue de proposições antecedentes pela uma lei (ou n + 3. P2 (linhas; lei)
várias leis) de Álgebra de Lógica, terminando com a ...
conclusão do argumento. k. C (Contradição)
Observação. Nos vários manuais, em vez do símbolo
` usa-se símbolo ∴ ou / ∴ (veja [2]). Consideremos, de novo, o argumento do Exemplo
5.9. A demonstração de validade directa para este ar-
Apresentemos a demonstração formal de validade gumento é (5.4). Apresentemos a demonstração de va-
para o argumento (5.1) do Exemplo 5.9 (i.e. demons- lidade indirecta para o mesmo argumento:
tração de validade pelo esquema (5.3):
1. M →R (Hip.) 1. M →R (Hip.)
2. A→B (Hip.) 2. A→B (Hip.)
3. (R ∨ B) → ¬D (Hip.) 3. (R ∨ B) → ¬D (Hip.)
4. D ` ¬M ∧ ¬A (Hip. ` Conclusão) 4. D ` ¬M ∧ ¬A (Hip. ` Conclusão)
5. ¬¬D (4; Dupla Negação 5. ¬(¬M ∧ ¬A) (Demonstração Indirecta)
6. ¬(R ∨ B) (3, 5; Modus Tollens) 6. ¬¬M ∨ ¬¬A (5; de Morgan))
(5.4) 7. M ∨A (6; Dupla Negação))
7. ¬R ∧ ¬B (6; de Morgan)
8. ¬R (7; Simplicação) 8. (M ∨ A) → (R ∨ B) (1, 2; Dilema Construtivo)
9. ¬B (7; Simplicação) 9. R∨B (7, 8; Modus Ponens)
10. ¬M (1, 8; Modus Tollens) 10. ¬D (3, 9; Modus Ponens)
11. ¬A (2, 9; Modus Tollens) 11. D ∧ ¬D ≡ C (4, 10; Contradição)
12. ¬M ∧ ¬A (10, 11; Def. de ∧)
Observamos, que as vezes é possível numa linha da
Para melhor compreensão, discutimos detalhada- demonstração formal usar duas leis, como foi feito na
mente sobre linha 5. Da disjunção das proposições linha 6 do exemplo.
30
5.4 Exemplos de demonstrações Resolução: Primeiro, escrevemos o argumento sim-
de validade bolicamente
31
Para cada um dos seguintes argumentos, dê uma de-
1. P → (Q → R) monstração directa e uma demonstração indirecta de
` ¬R → (P → ¬Q) (Hip. ` Conclusão) validade.
2. ¬(¬R → (P → ¬Q)) (Dem. Indirecta) 1.
3. ¬R ∧ ¬(P → ¬Q) (2; de Condicional 1) A ∨ (B ∧ C)
4. ¬R (3; Simplicação) B→D
5. ¬(P → ¬Q) (3; Simplicação) C→E
6. P ∧ ¬¬Q (5; de Condicional 1) D∧E →A∨C
7. P (6; Simplicação) ¬A ` C
8. ¬¬Q (6; Simplicação)
9. Q (8; Negação dupla) 2.
B ∨ (C → E)
10. Q→R (7, 1; Modus Ponens)
B→D
11. R (10, 9; Modus Ponens)
¬D → (E → A)
12. R ∧ ¬R ≡ C (11, 4; Contradição)
¬D ` C → A
Agora, mesmo que na terceira demonstração da Sec-
3.
ção 4.5, reduzimos (na base da lei de exportação) o (A ∨ B) → (A → D ∧ E)
teorema H para o teorema A∧D `E∨F
Sejam P → (Q → R), ¬R e P . Demonstrar ¬Q. 4.
Escrevamos o último teorema como o argumento A∨B
¬B ∨ C ` A ∨ C
1. P → (Q → R) (Hip.) 5.
2. ¬R (Hip.) (5.6) B∨C →B∧A
3. P ` ¬Q (Hip. ` Conclusão) ¬B ` ¬C
32
Apresentemos duas demonstrações: primeira, o governo controla os preços, R: eu sou rico, A: eu
usando parcialmente ideias e alguns passos da de- preocupo-me com o aumento dos preços).
monstração directa (em particular, a lei de Expor-
tação), e segunda, sem usar a lei de Exportação. 9. Se Wilson ou Alberto ganha, então Lúcio e Susana
choram. Susana não está chorada. Portanto, Al-
1. A∧B →C (Hip.) berto não ganhou.
2. (A → C) → D (Hip.) (W: Wilson ganha, A: Alberto ganha, L: Lúcia
3. ¬B ∨ E ` B → D ∧ E (Hip. ` Concl.) chora, S: Susana chora).
4. ¬(B → D ∧ E) (Dem.Indir.)
5. ¬¬(B ∧ ¬(D ∧ E)) (4; Cond.1b) 10. Se eu me escrevo neste curso e estudo bastante,
6. B ∧ ¬(D ∧ E) (5; Dupla neg.) então tiro boas notas. Se tiro boas notas, co feliz.
7. B ∧ (¬D ∨ ¬E) (6; de Morgan) Não estou feliz. Portanto, não me inscrevi neste
8. (B ∧ ¬D) ∨ (B ∧ ¬E) (7; Distr.) curso ou não estudei bastante.
9. ¬(B ∧ ¬E) (3; Dupla neg., de Morgan) (I: inscrevo-me neste curso, E: estudo bastante, B;
10. B ∧ ¬D (8, 9; Comut., Silog. disj.) tiro boas notas, F: estou feliz).
11. B∧A→C (1; Comut.
12. B → (A → C) (11; Exportação) 11. Hoje é um m de semana se e somente se hoje é
13. B→D (12, 2; Transitiva) Sábado ou Domingo. Portanto, hoje é um m de
14. ¬(B ∧ ¬D) (6; Cond.1b) semana, desde que hoje é Sábado. (F,S,D)
15. Contradição (10, 14; Contr.) 12. Hoje é um m de semana se hoje é Sábado ou Do-
mingo. Mas hoje não é um m de semana. Por-
1. A∧B →C (Hip.)
tanto, hoje não é Sábado e hoje não é Domingo.
2. (A → C) → D (Hip.)
(F,S,D)
3. ¬B ∨ E ` B → D ∧ E (Hip. ` Concl.)
4. ¬(B → D ∧ E) (Dem.Indir.) 13. Hoje é um m de semana somente se hoje é Sá-
5. ¬¬(B ∧ ¬(D ∧ E)) (4; Cond.1b) bado ou domingo. Hoje não é Sábado. Hoje não é
6. B ∧ ¬(D ∧ E) (5; Dupla neg.) Domingo. Portanto, hoje não é um m de semana.
7. B ∧ (¬D ∨ ¬E) (6; de Morgan) (F,S,D)
8. (B ∧ ¬D) ∨ (B ∧ ¬E) (7; Distr.)
9. ¬(B ∧ ¬E) (3; Dupla neg., de Morgan) 14. A proposta de auxílio está no correio. Se os arbi-
10. B ∧ ¬D (8, 9; Comut., Silog. disj.) tros a receberem até sexta-feira, eles a analisarão.
11. B (10; Simplif. Portanto, eles a analisarão, porque se a proposta
12. ¬D (10; Simplif.) estiver no correio, eles a receberão até sexta-feira.
13. ¬(A → C) (12, 2; Modos Tollens) (C,S,A)
14. ¬¬(A ∧ ¬C) (13; Cond.1b)
15. A ∧ ¬C (14; Dupla neg.) 15. Miau não é, ao mesmo tempo, um gato e um ca-
16. A (15; Simplif.) chorro. Miau é um gato. Logo, Miau não é um
17. ¬C (15; Simplif.) cachorro. (G,C)
18. A∧B (11, 16; Def de ∧)
19. ¬(A ∧ B) (1, 17; Modus Tollens) 16. Se Miau é um gato e Cléo um peixinho, então
20. Contradição (18, 19; Contr.) Fido não é um cachorro. Ou Fido é um ca-
chorro, ou Miau e Cléo gostam de nadar. Miau
Fim da resolução do Exercício 6. é um gato se e somente se Cléo é um peixinho.
7. Logo, se Miau é um gato, Miau gosta de nadar.
B → ¬S (MG,CP,FC,MN,CN)
D ∧ ¬P → S
D∧B `P 17. Se Miau caça, ele apanha ratos. Se ele não dorme
bastante, então ele caça. Se ele não apanha ratos,
Na demonstração de validade dos seguintes argumen- ele não dorme bastante. Logo, Miau apanha ratos.
tos, use os símbolos sugeridos. (C,R,D)
8. Se a população cresce rapidamente e a produção 18. Se Arlindo está doente, Mathias não vai à escola.
permanece constante, então os preços sobem. Se Se Mathias está doente, Arlindo não vai à escola.
os preços sobem, então o governo controla os pre- Arlindo e Mathias vão à escola. Logo, nem Arlindo
ços. Se sou rico, então não me preocupo com o au- nem Mathias estão doentes. (AD,MD,AE,ME)
mento dos preços. Não é verdade que não sou rico.
O governo não controla os preços ou preocupo-me 19. Se a Lua gira em torno da Terra e a Terra gira
com aumento dos preços. Portanto, não é verdade em torno do Sol, então Copérnico tinha razão. Se
que a população cresce rapidamente e a produção Copérnico tinha razão, então Ptolomeu não tinha
permanence constante. razão. A Terra gira em torno do Sol. Logo, se a
(P: a população cresce rapidamente, C: a produ- Lua gira em torno da Terra, Ptolomeu não tinha
ção permanence constante, S: os preços sobem, G: razão. (LT,TS,C,P)
33
20. Se meu cliente é culpado, então a faca estava na
gaveta. Ou a faca não estava na gaveta ou Jason
Pritchard viu a faca. Se a faca não estava lá no dia
10 de Outubro, então segue que Jason Pritchard
não viu a faca. Além disso, se a faca estava lá em
10 de Outubro, então a faca estava na gaveta e
também o machado estava no celeiro. Mas todos
nós sabemos que o machado não estava no celeiro.
Portanto, senhoras e senhores presentes no Juri,
meu cliente é inocente. (C,F,J,O,M)
34
Capítulo 6
Indução matemática
35
Então a proposição P (n) é verdadeira qualquer que seja Exemplo 6.3. Encontrar a soma
n ∈ N.
sn = 1 + 3 + 5 + . . . + (2n − 1).
O teorema 6.1 pode ser demonstrado na base de um
princípio de escolha. Notemos que o n-ésimo lugar ocupa o número 2n − 1
(que é possível demonstrar por meio da mesma indu-
O princípio de elemento mínimo: ção). Consideremos os cálculos:
k(k + 1)
Então, a proposição P (n) é verdadeira qualquer que
1 + 2 + ... + k = . seja n ∈ {m, m + 1, . . .}.
2
Baseando nesta hipótese demonstremos que para n = Exemplo 6.4. Demonstre que
k + 1 a proposição será válida também, isto é,
2n > n2
(k + 1)(k + 2)
1 + . . . + k + (k + 1) = . qualquer que seja n ≥ 5.
2
Temos Demonstração. Seja
36
Temos que demonstrar Então, a proposição P (n) é verdadeira para todos os
números n naturais.
P (k + 1) = {2k+1 > (k + 1)2 }.
Formulemos agora uma generalização do PIM fraco,
Usando hipótese obtemos usando a ideia do Teorema 6.2.
As vezes não é possível usar o princípio indicado. Mas (I) P (1) ∧ P (2) ∧ . . . ∧ P (k) → P (k + 1) qualquer que
pode ajudar o seguinte teorema. seja k ∈ {m, m + 1, . . .}.
Teorema 6.3 (PIM fraco). Suponhamos que Então, a proposição P (n) é verdadeira para qualquer
número n natural.
(B) P (1) é verdadeira;
Exemplo 6.7. Sejam s1 = 2, s2 = 4 e sn+2 = sn +
(I) P (1) ∧ P (2) ∧ . . . ∧ P (k) → P (k + 1) qualquer que sn+1 + 2n qualquer que seja n ∈ N. Demonstre que
seja k ∈ {1, 2, . . .}. sn = 2n qualquer que seja n ∈ N.
37
Demonstração. É preciso demonstrar P (n) = {sn =
2n } (∀n ∈ N). Apliquemos o Teorema 6.5 para m = 2.
(B) P (1) = {s1 = 21 } e P (2) = {s2 = 22 } são verda-
deiras.
Então, P (k + 1) é verdadeira.
Pelo PIM (Teorema 6.5), sn = 2n qualquer que seja
número natural n.
6.5 Exercícios
1. Demonstrar que para todos n ∈ N
1
(a) 12 + 22 + . . . + n2 = n(n + 1)(2n + 1),
6
an+1 − 1
(b) 1 + a + a2 + . . . + an = (a 6= 1)
a−1
(c) n5 − n é divisível por 10
(d) 11n − 4n é divisível por 7
2. Demonstrar para ∀n ∈ N
a ∨ (b1 ∧ b2 ∧ . . . ∧ bn ) ⇔
(a ∨ b1 ) ∧ (a ∨ b2 ) ∧ . . . ∧ (a ∨ bn )
(n = 2, 3, . . .),
(a1 → a2 ) ∧ (a2 → a3 ) ∧ . . .
∧(an−1 → an ) ⇒ (a1 → an ) (n = 2, 3, . . .),
38
Tema II
Conjuntos
39
Capítulo 7
conjuntos
40
seguida pelo símbolo 0 :0 ou pelo símbolo 0 |0 . A segunda Os números reais que não racionais chamam-se irra-
parte contém uma ou várias condições necessárias e cionais. O conjunto de números irracionais designa-se
sucientes para vericar se um elemento pertence ao por I.
conjunto. Em geral, a denição de um conjunto M Os exemplos nos númerosp irracionais são os números
√ 9 √
pala sua propriedade característica tem a forma notáveis π , e, também 2, 3 − 5, π 2 − 15.
Da Teoria de Números é conhecido que qualquer nú-
M = {x : P (x)}
mero real é representável na forma de uma fracção de-
onde P (x) um predicado. M é conjunto de tais x que cimal innita, sendo que esse numero é racional se e
a proposição P (x) seja verdadeira (seja válida a pro- somente se é representável na forma de uma fracção
priedade P (x)). decimal periódica.
Em Matemática usam-se várias formas da denição Por exemplo, o número 1 ∈ Q é representável na
por meio de uma propriedade característica. Em vez forma de uma fracção decimal periódica de dois méto-
de uma variável no primeiro lugar pode ser posta parte dos:
1 = 1.(0) = 1.000 . . . ou
das condições ou uma expressão. Assim,
1 = 0.(9) = 0.999 . . . ,
M = {x ∈ X : P (x)} o número 1 ∈ Q é representável na forma de uma frac-
3
signica: M é o conjunto de tais elementos x do con- ção periódica de um método:
junto X (pertencentes ao conjunto X ) que seja válida 1
P (x). = 0.(3) = 0.333 . . . ,
3
M = {f (x) : P (x)}
mas o número irracional π é representável so na forma
signica: M é conjunto de tais valores de f (x) que seja de uma fracção decimal não-periódica.
válida P (x). A natureza dos números irracionais não admite a
Consideremos, como exemplo, várias formas correc- determinação exacta de todos os dígitos na forma de
tas da denição (ou da representação) do conjunto D2 fracção não-periódica, mas admite uma aproximação
de números naturais pares: decimal desses números, que, com ajuda dos computa-
D2 = {2, 4, 6, . . .} dores modernos, pode ser muito boa! Por exemplo,
= {n : n ∈ N é par}
7.4 Conjuntos nitos e innitos.
= {n ∈ N : n é par}
Conjuntos equivalentes
= {n : (∃k ∈ N)n = 2k}
Existem conjuntos nitos e innitos, por exemplo o
= {n : n = 2k, k ∈ N} conjunto de todos os números naturais N é innito.
Designemos por P o conjunto de todos os números pri-
= {2n : n ∈ N} mos,
P = {2, 3, 5, 7, 11, 13, 17, 19, 23, . . .}. (7.1)
7.3 Conjuntos numéricos básicos O conjunto P é innito (veja Teorema G na Secção
4.4.2).
O conjunto
Usa-se o símbolo especial ∅ para o conjunto vazio que
N = {1, 2, 3, . . .}
não tem elementos.
é conjunto de números naturais. Para um conjunto nito A usa-se a notação |A| para
O conjunto o número dos elementos do A. Por exemplo, se A =
Z0 = {0, 1, 2, . . .} {a, b, c, d, e}, |A| = 5. Para mostrar, que |A| = |B| é
é conjunto de números inteiros não negativos. suciente e necessário estabelecer uma correspondência
O conjunto biunívoca entre estes conjuntos.
Diz-se que dois conjuntos são equivalentes se é possí-
Z = {0, ±1, ±2, . . .} vel estabelecer uma correspondência biunívoca. Então,
podemos dizer que dois conjuntos nitos A e B têm o
é conjunto de números inteiros. mesmo número de elementos, se A e B são equivalentes.
O conjunto Para conjuntos innitos pode acontecer que o con-
nm o junto pode ser equivalente à sua parte própria. Por
Q= :m∈Zen∈N exemplo, o conjunto N dos números naturais é equiva-
n
lente ao subconjunto dos números pares
é conjunto de números racionais.
Por R e C, como é habituado nos todos os ramos D2 = {2, 4, 6, 8, . . .}.
da Matemática vamos designar o conjunto de números
reais e complexos, respectivamente. Isto é impossível para conjuntos nitos.
41
Um conjunto que é equivalente ao conjunto N dos 7.5.4 Diferença dos sentidos de ∈ e ⊂
números naturais, diz-se enumerável, mas existem con-
juntos que não são enumeráveis. Por exemplo, é pos- Observamos, que na Teoria de Conjuntos (mesmo em
sível mostrar que o conjunto dos números reais R não todos ramos da Matemática) é preciso utilizar os sím-
é enumerável. Mas o conjunto Q de todos os núme- bolos ∈, 6∈, ⊂, e 6⊂ de modo exacto!
ros racionais é enumerável. Mais detalhadamente os 1) x ∈ A signica "x é elemento do conjunto A" ou
conjuntos enumeráveis vamos considerar no Tema IV. "o elemento x pertence ao conjunto A". Às vezes, em
dependência do contexto da frase, é correcto ler "x per-
tencendo ao A" ou mais curto "x do conjunto A". Por
exemplo, ∀x ∈ [0, 1] x2 + x > 0 pode-se ler como para
7.5 Inclusão. Conjunto univer- qualquer ponto x do segmento [0, 1] tem lugar a desi-
sal. Conjunto de conjuntos gualdade x2 + x > 0. Em alguns textos matemáticos
pode-se ver a expressão da forma A 3 x cujo signicado
7.5.1 Inclusão (⊂) é mesmo que x ∈ A.
2) x 6∈ A signica "x não é elemento do conjunto A"
Sejam A e B dois conjuntos. Se cada um dos elementos ou "o elemento x não pertence ao conjunto A".
x ∈ A é também elemento do conjunto B diz-se que A 3) A ⊂ B signica "A é subconjunto do conjunto B "
é um subconjunto do B , ou que o conjunto A é contido ou "o conjunto A está contido em B ". A descrição da
no conjunto B , e escreve-se expressão de palavras também depende do contexto.
Por exemplo, dado intervalo aberto ∆ ⊂ [0, 1] consi-
A ⊂ B. deremos ... entende-se como dado intervalo aberto ∆
contido no segmento [0, 1] consideremos ... Em alguns
A ultima relação A ⊂ B diz-se inclusão. textos matemáticos pode-se ver a expressão da forma
Por exemplo, temos uma sequência de inclusões: B ⊃ A cujo signicado é mesmo que A ⊂ B .
4) A 6⊂ B signica "A não é subconjunto do conjunto
{2, 3, 5} ⊂ P ⊂ N ⊂ Z0 ⊂ Z ⊂ Q ⊂ R ⊂ C. B " ou "o conjunto A não está contido em B ". É claro
que A 6⊂ B é equivalente a condição que os conjuntos
A e B c intersectam.
7.5.2 Conjunto universal
Exemplo 7.6. Sejam A = {1, 2, 3} e Ω = {{1}, {1, 2}}.
Frequentemente num problema consideram-se só sub- Então, é correcto escrever 1 ∈ A, 5 6∈ A, A 3 3,
conjuntos de um conjunto U dado, que se chama con- A ⊂ N, A ⊃ {1}, A ∈ P(Z), {1} ∈ P(A), Ω ⊂ P(A),
junto universo ou conjunto universal. Por exemplo, Ω ∈ P(P(A)). Mas é completamente incorrecto
as guras diferentes no plano podem ser consideradas escrever, por exemplo, 1 ⊂ A, {1} ∈ A, Ω ∈ N,
como subconjuntos dos pontos do plano. Neste caso o {1} ⊂ P(A) (porque?).
plano pode ser considerado como conjunto universal.
O conjunto de todos os números reais usa-se em aná-
lise matemática como conjunto universal para estudar 7.6 Operações sobre conjuntos
funções de uma variável real.
Seja dado um conjunto universal denotado por U . 7.6.1 Complemento
Neste caso o termo "um conjunto" signica "um sub- Uma das três operações de conjunto básicas é a opera-
conjunto do conjunto U , de outras palavras, A ⊂ U . ção de complemento. Apresentemos a denição exacta.
Denição 7.1.
Seja U um conjunto universal. Seja
7.5.3 Conjunto de conjuntos A um conjunto. O conjunto constituído de todos os
Seja M um conjunto. Usa-se designação P(M ) para o elementos de U que não são elementos de A, chama-
conjunto de todos os subconjuntos de M . Por exem- se complemento do conjunto A e designa-se A (nos
c
plo, seja M = {a, b, c}. O conjunto P(M ) contem 8 manuais diferentes também usam-se designações A e
elementos cA).
42
Se conside- Denição 7.6. Sejam A, B conjuntos. O conjunto
Exemplo 7.8. Seja A = {3, 4, 5, . . .}.
rar o conjunto universo N temos Ac = {1, 2}, mas constituído de todos os elementos que pertencem a um
se considerar o conjunto universo Z temos Ac = desses conjuntos e não pertencem a outro, chama-se
{0, ±1, ±2, −3, −4, . . .}. diferença simétrica dos conjuntos A e B e designa-se
Denimos duas operações básicas sobre conjuntos: A mesma denição na forma simbólica é:
união e intersecção.
def
Denição 7.2. Sejam A, B conjuntos. O conjunto A 4 B = {x : (x ∈ A ∧ x 6∈ B) ∨ (x ∈ B ∧ x 6∈ A)}.
constituído de todos os elementos que pertencem a pelo
menos um dos conjuntos A ou B chama-se união dos É claro que
conjuntos A e B e designa-se
A 4 B = (A r B) ∪ (B r A)
A∪B
Exemplo 7.11. Sejam A = {1, 2, 3} e B = {2, 3, 4}.
A mesma denição na forma simbólica é: Então,
def
A ∪ B = {x : x ∈ A ∨ x ∈ B}. A r B = {1}, B r A = {4},
Denição 7.3. Sejam A, B conjuntos. O conjunto A 4 B = {1, 4}.
constituído de todos os elementos que pertencem aos
ambos conjuntos A e B chama-se intersecção dos con- Exemplo 7.12. Sejam A = [0, 2] e B =]1, 3[. Então,
juntos A e B e designa-se
A∩B A r B = [0, 1], B r A =]2, 3[,
43
Exemplo 7.13. Visualize por meio do diagrama de Venn diz-se conjunto de verdade do predicado P (x).
o conjunto A ∪ (B ∩ C). Por outro lado, a cada conjunto A corresponde um
Resolução: predicado
P (x) = {x ∈ A}
tal que o conjunto de verdade do P (x) coincide com o
A.
Por exemplo, ao conjunto de todos os números pri-
mos corresponde o predicado
44
(i) A = P({a, b, c}) r P({a, b}) 10. Sejam A = [−1, 5], B = [−2, 0] e C = [−1, 4[.
(j) A = P({a, b, c}) ∩ P({a, c, d, e}) Esboce na recta numérica e escreva analiticamente
o conjunto (A r B) r C .
(k) A = {(−1)n : n ∈ Z r {2, 3, −5}}
(l) A = P({a, b, c, d}) r {∅} 11. Sejam A = [0, ∞[, B = [5, ∞[ e C = [2, 3]. Es-
boce na recta numérica e escreva analiticamente o
(m) A = P(P({a, b})) conjunto (A4B) ∪ C .
3. Visualize por meio do diagrama de Venn os seguin- 12. Sejam A = [0, 1[, B = [2, 5] e C =] − 9, 9[. Es-
tes conjuntos: A ∩ B ∩ C , A ∩ (B ∪ C), (B ∪ A) ∩ C , boce na recta numérica e escreva analiticamente o
Ar(B ∩C), Ar(B ∪C), A∪(B rC), Ar(B rC), conjunto (A ∩ C)4B .
(A r B) r C , A ∪ B ∪ C , A4(B ∩ C), A4(B ∪ C),
A∩(B4C), A∪(B4C), Ar(B4C), (ArB)4C , 13. Achar uma representação dos conjuntos a seguir
(A4B)4C . usando uma propriedade característica:
(a) A ∪ B , A ∩ C
(b) (A ∪ B) ∩ C c P = {Mercúrio, Vénus, Terra, Marte,
(c) A r B , C r D Júpiter, Saturno, Urânio, Neptuno}
(d) B 4 D
14. Suponhamos que o conjunto dos números naturais
e achar algumas representações dos conjuntos N é o conjunto universo. Listar os conjuntos
A, B, C, D usando propriedades características se
(a) A = {n : n2 < 50},
(a) O universo U é o conjunto de todos os núme- (b) B = A ∩ P onde P é o conjunto de todos os
ros naturais, números primos.
(c) C = {n : n < 20, né múltiplo de 3}
A = {1, 3, 5, 7, 9, 11}
B = {2, 3, 5, 7, 11} (d) D = A r C
C = {3, 6, 9, 12} 15. Sejam F e G os conjuntos das raízes reais das
D = {2, 4, 8} equações f (x) = x3 − 3x2 + 4x − 12 = 0 e
g(x) = x2 − 5x + 6 = 0 respectivamente. Achar
(b) U = R, i.e. R é universo, A = [0, 2], B = (a) o conjunto das raízes reais da equação
]3, 5], C =]2, ∞), D = {1, 4}. f (x)g(x) = 0
5. Seja U = {1, 2, . . . , 9} o universo, e sejam A = (b) o conjunto das raízes reais da equação f (x)2 +
{1, 2, 3, 4, 5}, B = {2, 4, 5, 6, 8}, D = {1, 4, 8, 9}. g(x)2 = 0
Encontre (liste) os seguintes conjuntos: (c) o conjunto das raízes reais da equação
(a) D ∪ (A r B)
c f (x)/g(x) = 0
6. Sejam A = [−3, 5[, B = [0, 1] e C = [−2, 2[. Es- A = {p : existem m e n tais que p = m2 + 2n2 }
boce na recta numérica e escreva analiticamente o
Verique que 0, 1, 2, 3, 4, 6, 8, 9 ∈ A, mas 5, 7 ∈
/ A.
conjunto (A ∩ B) ∪ C .
17. Seja F o conjunto de todas as raízes da equação
7. Sejam A = [0, ∞[, B =] − 2, 0] e C = [−3, 4].
f (x) = 0. O complemento F c é o conjunto das
Esboce na recta numérica e escreva analiticamente
soluções da f (x) 6= 0? Ou não? Pressupõe-se que
o conjunto (A r B) ∩ C .
o conjunto universal é R.
8. Sejam A = [1, 5], B =]1, 8] e C =] − ∞, 0[. Es- 18. Representar o conjunto P(P({a})) na forma de
boce na recta numérica e escreva analiticamente o uma lista.
conjunto (A ∪ B) r C .
19. Seja N o conjunto universo. Achar os conjuntos de
9. Sejam A = [0, 1[, B = [−1, 5] e C = [−3, 9[. Es- verdade dos predicados
boce na recta numérica e escreva analiticamente o
conjunto (A ∪ B) ∩ C . (a) S(n) ≡ {n é primo}
45
(b) P (n) ≡ {n é um número par}
(c) A(n) ≡ {n2 < 100}
(d) S(n) ∧ A(n)
(e) S(n) ∨ A(n)
(f) ¬S(n)
(g) P (n) → S(n)
(h) P (n) ↔ S(n)
20. Determine as operações sobre conjuntos corres-
pondentes às operações:
(a) Condicional →
(b) Bicondicional ↔
21∗ Entre todos os matemáticos cada sétimo é lósofo,
entre todos os lósofos cada décimo é matemático.
O que é maior, o número dos matemáticos ou ló-
sofos?
Resposta: lósofos
22∗ Sobre uma circunferência são marcados 2010 pon-
tos brancos e um ponto vermelho. Consideremos
todos polígonos possíveis com vértices nesses pon-
tos. Que número maior, o número dos polígonos
com ponto vermelho ou sem ponto vermelho?
Resposta: com ponto vermelho
23 Entre dos 40 estudantes de uma turma 32 estu-
∗
46
Capítulo 8
47
Demonstração. 10. A r B = A ∩ B c
x ∈ (A ∩ B) r (A ∩ C) 11. A 4 B = (A ∪ B) r (A ∩ B)
⇔ (x ∈ A ∧ x ∈ B)∧
¬(x ∈ A ∧ x ∈ C) (def. de ∩, r) 12. A r B = A r (A ∩ B) = (A ∪ B) r B
⇔ (x ∈ A ∧ x ∈ B)∧ 13. (A ∩ B) r C = A ∩ (B r C)
(x 6∈ A ∨ x 6∈ C) (Morgan.)
⇔ ((x ∈ A ∧ x ∈ B) ∧ x 6∈ A)∨ 14. A ∪ B = A ∪ (B r A) = (A r B) ∪ B =
((x ∈ A ∧ x ∈ B) ∧ x 6∈ C) (distr.) (A ∩ B) ∪ (A 4 B)
⇔ (Contr. ∧ x ∈ B)∨
(x ∈ A ∧ (x ∈ B ∧ x 6∈ C)) (Com,Ass,Cont) As leis 1-14 representam-se identidades dos conjun-
⇔ x ∈ A ∧ (x ∈ B ∧ x 6∈ C) (leis de Ident.) tos mais importantes. Um dos métodos de demonstra-
⇔ x ∈ A ∩ (B r C) (def. de ∩, r) ção das leis foi apresentado na secção anterior. Vamos
repetir este método e considerar um outro método de
Recomendação : Interpretar e sentir as igualdades demonstração.
dos exemplos por meio dos diagramas de Venn. 10 método (de raciocínio dedutivo). Para demons-
trar a lei (identidade) da forma A = B é suciente
demonstrar
8.2 Leis de álgebra de conjuntos x ∈ A ⇔ x ∈ B.
Suponhamos que todos os conjuntos são subconjuntos do método de raciocínio dedutivo usando denições das
de um conjunto U dado (conjunto universal). A seguir operações de conjuntos e leis da Álgebra Lógica.
são apresentadas as fórmulas que podem ser usadas Observamos que este método foi usado para demons-
como fórmulas básicas. Usando essas fórmulas pode- tração das leis 10, 11 e 12(1) nos Exemplos 8.78.8.
mos realizar transformações algébricas de maneira aná- Demonstramos, como exemplo, também a primeira lei
loga como fazem-se transformações em álgebra de nú- de Morgan:
meros. Pode-se demonstrar que o sistema apresentado (A ∪ B)c = Ac ∩ B c
é completo, isto é, pode ser tomado como um sistema Demonstração.
de axiomas na base do qual podia ser deduzida uma
fórmula qualquer. O sistema apresentado não é único, x ∈ (A ∪ B)c
existem outros sistemas equivalentes. ⇔ ¬(x ∈ A ∨ x ∈ B) (def. de compl., ∪, )
⇔ ¬(x ∈ A) ∧ ¬(x ∈ B) (Morgan)
1. Leis comutativas ⇔ x ∈ Ac ∩ B c (def. de compl., ∩, )
(a) A ∪ B = B ∪ A,
20 método (de transformações). A lei da forma
(b) A ∩ B = B ∩ A A = B demonstra-se pela cadeia (sequência) nita das
identidades
2. Leis associativas
(a) (A ∪ B) ∪ C = A ∪ (B ∪ C), A = M1 = M2 = . . . = Mn = B
(b) (A ∩ B) ∩ C = A ∩ (B ∩ C) onde a cada passo deduzimos com base de uma lei de
Teoria de Conjuntos, já conhecida.
3. Leis distributivas
Como exemplo, demonstramos a lei 11
(a) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C),
A 4 B = (A ∪ B) r (A ∩ B)
(b) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
do método de transformações (veja a demonstração do
4. A ∪ A = A, A∩A=A
método de raciocínio dedutivo no Exemplo 8.8).
5. (a) A ∪ ∅ = A Demonstração.
(b) A ∪ U = U
A4B
(c) A ∩ ∅ = ∅ = (A r B) ∪ (B r A) (def. de 4, )
(d) A ∩ U = A = (A ∩ B c ) ∪ (B ∩ Ac ) (lei 10)
= (A ∪ B) ∩ (A ∪ Ac )∩
6. (Ac )c = A (B c ∪ B) ∩ (B c ∪ Ac ) (lei distr. duas vezes)
7. A ∪ Ac = U, A ∩ Ac = ∅ = (A ∪ B) ∩ U ∩ U
∩(Ac ∪ B c ) (leis comut. e 7)
8. U c = ∅, ∅c = U = (A ∪ B) ∩ (A ∩ B)c (leis 4,5 e de Morgan)
= (A ∪ B) r (A ∩ B) (lei 10)
9. Leis de Morgan
A identidade do Exemplo 8.10
(a) (A ∪ B)c = Ac ∩ B c ,
(b) (A ∩ B)c = Ac ∪ B c A ∩ (B r C) = (A ∩ B) r (A ∩ C)
48
também demonstramos do método das transformações A segunda inclusão segue da primeira e da lei co-
de dois modos diferentes: mutativa: A ∪ B = B ∪ A.
Demonstração 1.
(A ∩ B) r (A ∩ C)
Lema 2. A ∩ B ⊂ A e A ∩ B ⊂ B .
= (A ∩ B) ∩ (A ∩ C)c (lei 10)
= (A ∩ B) ∩ (Ac ∪ C c ) (lei de Morgan)
Demonstração.
= ((A ∩ B) ∩ Ac ) ∪ ((A ∩ B) ∩ C c ) (distr.) x∈A∩B
= (B ∩ ∅) ∪ (A ∩ (B ∩ C c )) (leis com.,ass. e 7) ⇔ x∈A∧x∈B (def. de ∩, )
= A ∩ (B ∩ C c ) (leis 5) ⇒ x∈A (lei de simplicação)
= A ∩ (B r C) (lei 10)
Demonstração 2. A segunda inclusão segue da primeira e da lei co-
mutativa: A ∩ B = B ∩ A.
A ∩ (B r C)
= (A ∩ B) r C (lei 13) I. Demonstramos A ⊂ B ⇔ A ∪ B = B .
= (A ∩ B) r (A ∩ B ∩ C) (lei 12)
1) Primeiro, provamos A ⊂ B ⇒ A ∪ B = B .
= A ∩ (B r (A ∩ B ∩ C)) (lei 13)
= A ∩ (B r (B ∩ (A ∩ C))) (leis com. e ass.) Seja A ⊂ B .
= A ∩ (B r (A ∩ C)) (lei 12) (a) A inclusão B ⊂ A ∪ B segue do Lema 1.
= (A ∩ B) r (A ∩ C) (lei 13)
(b) Demonstramos à inclusão A ∪ B ⊂ B do mé-
Observação. O método de raciocínio dedutivo é mais todo de raciocínio dedutivo (é conveniente usar
universal do que método das transformações, mas, a linguagem matemática mista, e não apenas es-
quando é possível usar o segundo, ele é, como regra, quema formal).
mais racional do que primeiro. Seja x ∈ A ∪ B . Então, pela denição x ∈ A ou
Exemplo 8.11. (Exercício 9(a) em [L]). Demonstrar x ∈ B.
A ∩ (B 4 C) = (A ∩ B) 4 (A ∩ C). Caso 1. Seja x ∈ A. Da inclusão A ⊂ B segue
(x ∈ A) → (x ∈ B). Então (pelo lei de modus
Demonstração. Ponens) x ∈ B .
A ∩ (B 4 C) Caso 2. Seja x ∈ B . A proposição x ∈ B é imedi-
= A ∩ ((B r C) ∪ (C r B)) (def. de 4) ata.
= (A ∩ (B r C)) ∪ (A ∩ (C r B)) (lei distr.)
A inclusão A ∪ B ⊂ B está demonstrada.
= ((A ∩ B) r (A ∩ C))∪
((A ∩ C) r (A ∩ B)) (Ex. 8.10) Das inclusões em (a) e (b) segue A ⊂ B ⇒ A∪B =
= (A ∩ B) 4 (A ∩ C) (def. de 4) B.
2) Em segundo, provamos A∪B = B ⇒ A ⊂ B .
8.3 Exercícios Seja A ∪ B = B .
49
5. Demonstre que para quaisquer conjuntos A, B, C : 1o caso. Seja x ∈ A. Como A ⊂ C temos x ∈ C .
Então, x ∈ C ∪ D.
(a) Ac r B = (A ∪ B)c
2o caso. Seja x ∈ B . Como B ⊂ D temos x ∈ D.
(b) A ∩ (B r A) = ∅ Então, x ∈ C ∪ D.
(c) A ∪ (B r A) = A ∪ B
Proposição C. A r B ⊂ (A r C) ∪ (C r B).
(d) (A4B)c = (A ∩ B) ∪ (A ∪ B)c
Demonstração.
(e) A r (B ∪ C) = (A r B) ∩ (A r C)
(f) A r (B ∩ C) = (A r B) ∪ (A r C) ArB
= A ∩ Bc (lei 10)
(g) (A ∪ B) r C = (A r C) ∪ (B r C)
= A ∩ B c ∩ (C ∪ C c ) (leis 7,5)
(h) (A ∩ B) r C = (A r C) ∩ (B r C) = ((A ∩ B c ) ∩ C) ∪ ((A ∩ B c ) ∩ C c ) (distr.)
= ((A ∩ C c ) ∩ B c ) ∪ ((C ∩ B c ) ∩ A) (comut. e ass.)
6. É verdade que a igualdade é válido para quaisquer
⊂ (A ∩ C c ) ∪ (C ∩ B c ) (Prop. A,B)
subconjuntos A, B, C de um conjunto universo U ?
= (A r C) ∪ (C r B) (lei 10)
No caso sim demonstre, mas no caso não apresente
um contra-exemplo. Agora, demonstramos a inclusão do Exercício 8b.
(a) A ∩ (B ∪ C) = (A ∩ B) ∪ C A4B
(b) A ∪ (B ∩ C) = (A ∪ B) ∩ C = (A r B) ∪ (B r A) (def. de 4)
(c) A r (B ∩ C) = (A r B) ∩ (A r C) ⊂ ((A r C) ∪ (C r B))∪
((B r C) ∪ (C r A)) (Prop. C,B)
(d) (A r B) r C = A r (B r C)
= ((A r C) ∪ (C r A))∪
(e) A r (B r A) = A ((B r C) ∪ (C r B)) (comut. e ass.)
(f) A r (A r B) = A ∩ B = (A 4 C) ∪ (A 4 C) (def. de 4)
(g) A r (A r B) = B
(h) Ac r B c = B r A
(i) A ∪ (B4C) = (A ∪ B)4(A ∪ C)
(j) P(A ∩ B) = P(A) ∩ P(B)
(k) P(A ∪ B) = P(A) ∪ P(B)
(l) P(A r B) = P(A) r P(B)
Resposta. não, não, não, não, sim, sim, não, sim,
não, sim, não, não
7. Demonstrar as leis de Morgan
8. Provar a generalização da lei de Morgan
(A ∩ B ∩ C)c = Ac ∪ B c ∪ C c
50
Capítulo 9
S × T = {(s, t) : s ∈ S ∧ t ∈ T }. {Ai : i ∈ I}
é uma família indexada de conjuntos, sendo I o con-
Se S = T escreve-se também S × S = S 2 . junto dos índices.
Exemplo 9.1. Sejam S = {1, 2, 3, 4}, T = {a, b, c}. Pro- Uma família de conjuntos diz-se não vazia se o con-
duto S × T consiste das 12 pares ordenados: junto dos índices for não vazio (mas não impede que
um dos elementos da família seja o conjunto vazio).
(1, a) (2, a) (3, a) (4, a) O conjunto dos indexes pode ser nito ou innito, e,
(1, b) (2, b) (3, b) (4, b) respectivamente, a mesma família indexada de conjun-
(1, c) (2, c) (3, c) (4, c). tos indexados é familia nita ou innita.
1. No caso da familia nita é confortável como um
Exemplo 9.2. Sejam M = [0, 1], N = (0, 2). O produto conjunto de índices usar os primeiros números naturais,
M × N é o conjunto a partir de 1. Por exemplo, a familia de n conjuntos
diferentes pode ser indexada por meio do conjunto de
{(x, y) : 0 ≤ x ≤ 1, 0 < y < 2}. índices I = {1, 2, . . . , n}, tal que a família tem a forma
{Ai : i = 1, 2, . . . , n} = {Ai : i = 1, n}.
Então, podemos imaginar este conjunto geometrica-
mente como o rectângulo com os lados 1 e 2. Notemos Exemplo 9.3. Indexar a família de conjuntos
que dos lados direita e esquerda o rectângulo é fechado, F = {∅, N, Z0 , Z, Q, R}
mas em cima e em baixo é aberto.
(onde Z0 = N ∪ {0}) pode-se da seguinte maneira:
Em caso geral S × T 6= T × S .
Para o número de elementos do conjunto S usa-se a F = {Ai : i = 1, 2, 3, 4, 5, 6}
designação |S|. É claro que onde A1 = ∅, A2 = N, A3 = Z0 , A4 = Z, A5 = Q e
A 6 = R.
|S × T | = |S| · |T |.
Notemos que a nossa família indexada satisfaz a pro-
priedade:
Generalização:
Ai ⊂ Ai+1
Em geral, uma família indexada de conjuntos que sa-
S1 × . . . × Sn
tisfaz a esta propriedade, chama-se família monótona.
= {(s1 , s2 , . . . , sn ) : sk ∈ Sk , k = 1, 2, . . . , n}. É claro que é possível indexar a família F de outra
maneira (neste caso obtemos a família não monótona).
No caso 2. Para indexar uma família de conjuntos innita
S1 = S2 = . . . = Sn = S usam-se vários conjuntos dos índices. Se a família
é enumerável (existe correspondência biunívoca entre
usa-se designação elementos da família e N), então, como regra, usam-se
conjuntos dos índices N, Z0 ou Z (mas não sempre só
S × S × . . . × S = Sn. estes!).
51
Exemplo 9.4. A cada n ∈ N associemos o cubo Cn = No caso da família indexada {Ai : i ∈ I} para união
[0, n]3 (faça o esboço!). Obtemos assim a família inde- desta família (união de todos os conjuntos da família)
xada usa-se também a designação
{Cn : n ∈ N}.
∪ Ai .
Notemos que esta família é monótona. i∈I
Exemplo 9.7. A cada (m, n) ∈ N2 associemos o subcon- (o conjunto dos elementos cada um dos quais pertence
junto Dm,n = [m, 2m] × [n, 2n] do conjunto R2 (rectân- a todos conjuntos da família F ).
gulo fechado, faça o esboço!). Obtemos assim a família
No caso da família indexada {Ai : i ∈ I} para inter-
indexada
secção desta família (intersecção de todos os conjuntos
{D : m, n ∈ N} = {D : (m, n) ∈ N2 } da família) usa-se também a designação
m,n m,n
∩ Ai .
(indexada por meio dos índices duplos ). i∈I
e quando I = N as designações
9.2.1 Generalização das operações de ∞
união e intersecção ∩ Ak = A1 ∩ A2 ∩ . . .
k=1
Denição 9.2. Seja F uma família arbitrária de con- Teorema 9.1. Para qualquer família indexada de con-
juntos. Dene-se a união desta família, que se denota juntos {Ai : i ∈ I} são válidas as seguintes proposições:
por
∪F ou ∪A∈F A ou ∪ A, ∀(i ∈ I) Ai ⊂ B ⇔ ∪ Ai ⊂ B,
A∈F i∈I
B ⊂ ∩ Ai ⇔ ∀(i ∈ I) B ⊂ Ai .
do seguinte modo: i∈I
52
∞
Exemplo 9.10. Demonstre que ∪ = (0, 1]. 2. Represente o conjunto na forma de uma lista. De-
1
n, 1
n=1
termine |A|.
Resolução. Sejam An = n , 1 (n ∈ N). É claro que
1
An ⊂ (0, 1] qualquer que seja n ∈ N. Pelo Teorema (a) A = (N ∩ [1, 3]) × (Z ∩ [−2, −1])
9.1, (b) A = (Z∩] − 2, 3])2
∞
∪ An ⊂ (0, 1]. (9.1)
n=1
3. Sejam A = [0, 2], B = [2, 3[, C =]1, 2[. Achar e
Reciprocamente, seja x ∈ (0, 1]. Então, existe m ∈ N construir os produtos directos
(sucientemente grande) tal que m 1
< x. Temos que
∞ A × B, (A r C) × (B r C).
x ∈ Am . Pela denição da união, x ∈ ∪ An . Pela
n=1
denição da inclusão,
4. Sejam A = [0, 3], B = [1, 4]. Construir o conjunto
∞
(0, 1] ⊂ ∪ An . (9.2)
n=1 {(x, y) ∈ A × B : y > x2 }.
Das inclusões (9.1) e (9.2) implica a igualdade que que-
riam demonstrar. 5. Sejam A = {a, b, c}, B = {3, 5}, C = {4, 5}.
Achar
9.2.2 Leis generalizadas (a) A × (B ∪ C)
Algumas leis de álgebra de conjuntos admitem genera- (b) A × (B ∩ C)
lização para famílias de conjuntos. Apresentamos estas (c) (A × B) ∪ (A × C)
leis conservando a numeração da Secção 6.6 de [L].
Sejam U conjunto universo e B um subconjunto de (d) (A × B) ∩ (A × C)
U . Seja {Ai i ∈ I} uma família de conjuntos arbitrária.
6. Seja U = {1, 2, . . . , 9} o universo, e sejam A =
Observamos, primeiro, que para uniões e intersecções
{1, 2, 3, 4, 5}, B = {2, 4, 5, 6, 8}, D = {1, 4, 8, 9}.
das famílias de conjuntos são válidas leis comutativa e
Encontre (liste) os seguintes conjuntos:
associativa (a formulação destas leis é evidente).
3∗ Leis distributivas generalizadas (a) (A ∩ B) × D
(b) (A r D) × B
(a) B ∪ ∩ Ai = ∩ (B ∪ Ai ) (c) (A × B) r D2
i∈I i∈I
(d) (A r B) × Dc
(b) B ∩ ∪ Ai = ∪ (B ∩ Ai )
i∈I i∈I (e) (D × B) ∩ A2
9∗ Leis de Morgan generalizadas (f) A2 4B 2
c (g) (A ∩ B) × (D r A)
(a) ∪ Ai = ∩ Aci
i∈I i∈I
c 7. Sejam A = [−3, 5[, B = [0, 1] e C = [−2, 2[. Es-
boce no plano cartesiano e escreva analiticamente
(b) ∩ Ai = ∪ Aci
i∈I i∈I sem o uso das operações de conjuntos diferentes
de × e ∪, o conjunto (A × B) ∩ (C × A).
Demonstração da lei 9∗ (a).
c 8. Sejam A = [1, 5], B =]1, 8] e C =] − ∞, 0[. Esboce
x ∈ ∪ Ai no plano cartesiano e escreva analiticamente sem
i∈I o uso das operações de conjuntos diferentes de ×
⇔ ¬ x ∈ ∪ Ai (def. de compl.) e ∪, o conjunto (B × B) ∩ (A × C).
i∈I
⇔ ¬∃(i ∈ I) x ∈ Ai (def. de ∪) 9. Sejam A = [−1, 5], B = [−2, 0] e C = [−1, 4[. Es-
⇔ ∀(i ∈ I) x 6∈ Ai (Morgan) boce no plano cartesiano e escreva analiticamente
⇔ ∀(i ∈ I) x ∈ Aci (def. de compl.) sem o uso das operações de conjuntos diferentes
⇔ x ∈ ∩ Aci (def. de ∩) de × e ∪, o conjunto (A × A) r (B × B).
i∈I
53
∞
12. Sejam A = [−1, 3], B = [1, 5] e C = {0, 1, 2}. Es- (b)
1
∩ 0, n
boce no plano cartesiano e escreva analiticamente n=1
∞
sem o uso das operações de conjuntos diferentes (c) 0, n1
∪
de × e ∪, o conjunto (A × B)4(B × A). n=1
∞
(d) ∪ [2−n , 1 − 2−n ]
13. Sejam A = [0, 1[, B = [2, 5] e C =] − 9, 9[. Esboce n=1
no plano cartesiano e escreva analiticamente sem ∞
(e) ∩ − n12 , 3 + 1
o uso das operações de conjuntos diferentes de × n=1 n+5
e ∪, o conjunto (B × B) r (A × C). 9
(f)
1
∩ 0, n
n=1
14. Seja A = B ∩ C . Mostrar que ∞
(g) ∪ [−n, ln n]
n=2013
(a) A × A = (B × B) ∩ (C × C) ∞
(h) 1 + n1 , 3 + 3
(b) A × A = (B × C) ∩ (C × B) ∪ n
n=1
∞
(i) 1 + n1 , 3 + 3
15. Demonstre a lei: ∩
n=1 n
(a) (A ∩ B) × (C ∩ D) = (A × C) ∩ (B × D)
(b) (A ∪ B) × (C ∪ D) = (A × C) ∪ (B × D)
(c) A2 r B 2 = (A r B)2
54
Tema III
Relações e Funções
55
Capítulo 10
Relações
10.1 Predicados de duas variá- Denição 10.1 (Relação). Sejam A e B dois conjun-
veis tos. Qualquer subconjunto R ⊂ A × B diz-se relação
de A para B .
Seja P (x, y) um predicado de dias variáveis proposici- Notemos que R pode ser chamada relação binária.
onais x e y denidas sobre os conjuntos A e B respec- A relação R determina o predicado
tivamente (tal que x ∈ A e y ∈ B ).
O conjunto de verdade R(x, y) ≡ {(x, y) ∈ R}
56
Denição 10.5 (Composição de relações). Sejam R
uma relação de A para B e S uma relação de B para
C . A composição S ◦ R das relações R e S é
S ◦ R = {(x, z) ∈ A × C :
∃y ∈ B((x, y) ∈ R ∧ (y, z) ∈ S)}
Resolução: Como os conjuntos X, Y, Z são nitos, é É fácil ver que qualquer que seja relação R ⊂ A × B
cómodo usar o método de diagramas. têm lugar R ◦ iA = R e iB ◦ R = R.
57
Denição 10.7. Seja R uma relação de A para A. A 10.6 Exercícios
relação R diz-se:
a) reexiva (R) se 1. Achar os domínios e as imagens das relações de-
nidas a seguir.
(x, x) ∈ R
(a) m < n no conjunto N, isto é,
qualquer que seja x ∈ A;
b) simétrica (S) se M = {(m, n) : m < n}.
{(m, n) ∈ N × N : m − n é múltiplo de 3} R = {(1, 4), (1, 5), (2, 5), (3, 6)}
58
(a) T −1 ◦ (S ◦ R) 11. Demonstrar o teorema 10.2.
(b) R ◦ (T −1
◦ S) 12. Verique se as relações são (R), (S), (T), (AS)?
(c) S −1
◦ (R ◦ T ) Quais das relações são de equivalência e quais são
(d) S ◦ (R ◦ T −1 ) de ordem parcial?
(e) S −1 ◦ (T ◦ R−1 ) (a) a relação Ra de paralelismo a k b no conjunto
(f) R −1
◦ (S −1
◦ T) de todas as rectas no espaço;
(g) T ◦ (R ◦ S) (b) a relação Rb de perpendicularidade a⊥b no
conjunto de todas as rectas no espaço;
5. Apresente o esboço e ache o domínio e o contra-
(c) Rc = {(m, n) ∈ N × N : |m − n| ≤ 1}
domínio da relação R ⊂ R × R denida por:
(d) Rd = {((m, n), (k, l)) ∈ N2 × N2 : m − n =
(a) R = {(x, y) : 0 < y < x} k − l};
(b) R = {(x, y) : x < y < 2x} (e) Re = {(m, n) ∈ N × N: m −
(c) R = {(x, y) : 3x < y < x} n é múltiplo de 4};
(f) Rf = {(m, n) ∈ N × N : ∃k ∈ Z m = 2k n };
(d) R = {(x, y) : y − 1 = |x|}
(e) R = {(x, y) : x2 + y 2 < 1} (g) Rg = {(m, n) ∈ Z × Z : m2 = n2 };
(f) R = {(x, y) : x2 + y 2 ≥ 1} (h) A = {a, b, c}, Rh ⊂ A × A, R =
(g) R = {(x, y) : xy = 1} {(a, a), (b, a), (b, b), (b, c), (c, c)};
Dr ◦ Ds .
59
Capítulo 11
Funções
60
Teorema 11.2 (associatividade da composição). Se- Teorema 11.3. Seja f : X → Y . Consideremos a
jam dadas três funções f : X → Y , g : Y → Z e equação
h : Z → T . Então, h ◦ (g ◦ f ) = (h ◦ g) ◦ f . f (x) = y (11.3)
Exemplo 11.3. Sejam f, g : R → R, em relação à incógnita x ∈ X .
x
f (x) = x2 , g(x) = 2 . 1. A função f é injectiva se e somente se qualquer
x +1
que seja parte direita y ∈ Y a equação (11.3) ad-
Achar as funções g ◦ f e f ◦ g e comprar. mite no máximo uma solução (a equação tem a
Resolução. Temos propriedade de unicidade de solução).
Observação. Para qualquer função f : X → Y é 2. A função f : [0, ∞[→ R denida pela fórmula
habituado dizer que f é uma função (ou actua) de X (11.4) é injectiva mas não é sobrejectiva.
em Y , mas caso de f sobrejectiva também dizem-se que
3. A função f : R → [0, ∞[ denida pela fórmula
f é uma função (ou actua) de X para Y . Então, em
(11.4) é sobrejectiva mas não é injectiva.
diferença das relações, no caso de funções o conectivo
de linguagem "para" pode ser usado exclusivamente no 4. A função f : R → R denida pela fórmula (11.4)
caso das funções sobrejectivas. não é injectiva nem sobrejectiva.
Denição 11.4 (Bijecção). Uma função f : X → Y
é chamada bijectiva (ou bijecção, ou correspondência
biunívoca ) se é injectiva e sobrejectiva. 11.4 Funções inversas
As propriedades de injectividade, sobrejectividade e Seja f : X → Y . A relação inversa f −1 sempre existe:
bijectividade de uma função admitem descrição equi-
valente nos termos das equações. f −1 = {(y, x) : (x, y) ∈ f } = {(y, x) : y = f (x)}.
61
Denição 11.5. Uma função f : X → Y diz-se inver- 11.5 Imagem e pré-imagem de
sível se a relação inversa f −1 é uma função de Y em
X.
conjunto
Para uma função inversível f : X → Y a função Da denição de imagem de relação vamos ter a seguinte
f −1 : Y → X é chamada função inversa de f . forma de imagem de função:
Teorema 11.6. Uma função f : X → Y é inversível Teorema 11.8 (propriedades de imagem). Seja f :
se e somente se é uma função bijectiva. X → Y uma função, A, A1 , A2 ⊂ X e Ai ⊂ X (α ∈ I)
onde I algum conjunto de índices (nito ou innito).
Antes da formulação do segundo critério notemos Então, são válidas as seguintes proposições:
que a relação de identidade iX = {(x, x) : x ∈ X} é (a) f (∅) = ∅ e f (X) = Im(f );
uma função inversível e dena-se por iX (x) = x.
(b) Se f é injectiva e f (A1 ) = f (A2 ), então A1 = A2 ;
Teorema 11.7. Uma função f : X → Y é inversível
se e somente se existe existe uma função g : Y → X (c) f (∪i∈I Ai ) = ∪i∈I f (Ai );
tal que
(d) f (∩i∈I Ai ) ⊂ ∩i∈I f (Ai );
g ◦ f = iX , f ◦ g = iY , (11.5)
(e) Se f é injectiva, então f (∩i∈I Ai ) = ∩i∈I f (Ai );
ou, o que é o mesmo,
(f) f (A1 r A2 ) ⊃ f (A1 ) r f (A2 );
g(f (x)) = x (∀x ∈ X), f (g(y)) = y (∀y ∈ Y ).
(g) Se f é injectiva, então f (A1 rA2 ) = f (A1 )rf (A2 ).
Mais ainda, no caso (11.5) temos f −1
= g. Denição 11.7 (Pré-imagem). Seja f : X → Y uma
função e B ⊂ Y . O conjunto
Observação 1. Nas algumas áreas da Matemática
uma função inversível f : X → X chama-se transfor- f −1 (B) = {x ∈ X : f (x) ∈ B}.
mação do conjunto X .
chama-se pré-imagem (ou imagem inversa, ou imagem
Observação 2. Nas algumas áreas da Matemática recíproca) do conjunto B pela função f (ou sob a fun-
uma função f : X → Y chama-se inversível se é apenas ção f ).
injectiva. Neste caso a função inversa que denotemos
por f1−1 dena-se como função de Im f para X que No exemplo 11.1 f −1 ({1, 2}) = {a, c}.
satisfaz as condições:
Teorema 11.9 (propriedades de pré-imagem). Seja
f1−1 (f (x)) = x (∀x ∈ X), f (f1−1 (y)) = y (∀y ∈ Im f ). f : X → Y uma função, B, B1 , B2 ⊂ Y e Bi ⊂ Y
(α ∈ I) onde I algum conjunto de índices (nito ou
A justicação desta denição é o seguinte: se rede- innito). Então, são válidas as seguintes proposições:
nir à função f , ou seja consider a função f1 : X → Im f (a) f −1 (∅) = ∅ e f −1 (X) = f −1 (Im(f )) = X ;
denida por f1 (x) = f (x) (x ∈ X), então f1 já será in-
jectiva e sobrejectiva, logo será inversível com a inversa (b) Se f é sobrejectiva e f −1 (B1 ) = f −1 (B2 ), então
f1−1 : Im f → X no sentido da denição 11.5. B1 = B2 ;
Mas se a função f não é injectiva, então, já é princi-
(c) f −1 (∪i∈I Bi ) = ∪i∈I f −1 (Bi );
palmente impossível redenir a f de modo que a relação
inversa seja uma função. (d) f −1 (∩i∈I Bi ) = ∩i∈I f −1 (Bi );
Nós sempre vamos usar as noções de função inversí-
vel e de função inversa no sentido da denição 11.5. (e) f −1 (B1 r B2 ) = f −1 (B1 ) r f −1 (B2 );
62
Teorema 11.10 (propriedades de imagem e pré-ima- 3. Seja A = {2, 3, 4, . . .}. Seja
gem). Seja f : X → Y uma função, A ⊂ X e B ⊂ Y .
a | b = {a é divisor do b}.
Então, são válidas as seguintes proposições:
Verique que a relação M ⊂ A × A,
(a) f −1 (f (A)) ⊃ A;
M = {(x, d) : d | x ∧ ∀d1 (d1 < d → ¬(d1 | x))}
(b) Se f é injectiva, então f −1 (f (A)) = A;
é função. Encontre os valores
(c) f (f −1 (B)) ⊂ B ;
M (10), M (101), M (1001).
(d) Se f é sobrejectiva, então f (f −1 (B)) = B .
4. Verique que a relação de identidade iA ⊂ A × A,
Observação. Recomendemos demonstrar as propo-
sições dos Teoremas 11.8, 11.9 e 11.10 (veja exercícios iA = {(x, x) : x ∈ A}
22-28 abaixo). Notemos que inclusões ⊃ e ⊃ desses te-
é uma função.
oremas, em geral, não é possível alterar para igualda-
des! A construção dos contra-exemlos correspondentes 5. Sejam A = {1, 2, 3}, B = P(A) e f : B → B
é parte do exercício 28. dena-se por
f (X) = A r X.
11.6 Exercícios Ache f ({1, 3}).
11.6.1 Exercícios (secção 11.1) 6. Sejam A = B = [−2, 2]. Consideremos as relações
f, g ⊂ A × B denidas por f = {(x, y) : x − y = 1}
1. Para as relações seguintes indicar se são funções e g = {(x, y) : x − y ≤ 1}. Verique (justicando)
ou não: se as relações f e g são funções de A em B ou não.
(a) A = B = {1, 2, 3}, f, g, h ⊂ A × B , Para aquelas que são funções, calcule o valor da
função no ponto −1.
f = {(1, 1), (1, 2), (1, 3)}
7. Sejam A = B = [−1, 1]. Consideremos as relações
g = {(1, 1), (2, 1), (3, 1)} f, g ⊂ A × B denidas por f = {(x, y) : x2 + y =
h = {(1, 1), (2, 1)} 1, x ≥ 0} e g = {(x, y) : x2 + y = 1, y ≤ 0}.
Verique (justicando) se as relações f e g são
(b) f1 , f2 , f3 ⊂ I × I , onde I = [−5, 5], funções de A em B ou não. Para aquelas que são
funções, calcule o valor da função no ponto 0.
f1 = {(x, y) : x2 + y 2 = 25}
8. Sejam A = B = [−3, 3]. Consideremos as relações
f2 = {(x, y) : x2 + y 2 = 25, x ≥ 0}
f, g ⊂ A × B denidas por f = {(x, y) : x2 + y =
f3 = {(x, y) : x2 + y 2 = 25, y ≤ 0} 1, x ≤ 0, y ≥ 0} e g = {(x, y) : x2 +y = 1, y < 0}.
f4 = {(x, y) : x2 + y 2 = 25, xy ≥ 0} Verique (justicando) se as relações f e g são
funções de A em B ou não. Para aquelas que são
f5 = f4 r {(0, 5)}
funções, calcule o valor da função no ponto 2.
(c) Sejam C o conjunto de todas as cidades, N o 9. Sejam A = B = R. Consideremos as relações
conjunto de todos os países, L ⊂ C × N , f, g ⊂ A × B denidas por f = {(x, y) : x = cos y}
e g = {(x, y) : y = cos x}. Verique (justicando)
L = {(c, n) : a cidade c é do pais n} se as relações f e g são funções de A em B ou não.
Para aquelas que são funções, calcule o valor da
(d) Sejam P o conjunto de todas as pessoas, C ⊂ função no ponto π .
P × P,
10. Sejam A = N2 e B = N e seja a|b =
C = {(p, q) : p é progenitor do q}. {a é divisor do b}. Consideremos a relação f ⊂
A × B denida por f = {((x, y), d) : d|x ∧ d|y ∧
(e) Sejam P o conjunto de todas as pessoas, D ⊂ ∀d1 (d1 > d → ¬(d1 |x ∧ d1 |y))}. Verique (justi-
P × P(P ), cando) se a relação f é uma função de A em B
ou não. Caso sim calcule o valor de f no ponto
D = {(p, x) : (12, 15).
x é o conjunto de todos os lhos do p}.
11. Sejam A = N2 e B = N e seja a|b =
{a é divisor do b}. Consideremos a relação f ⊂
2. Verique que f ⊂ R × R,
A × B denida por f = {((x, y), m) : x|m ∧ y|m ∧
f = {(x, y) : xy = 1 ∨ (x = y = 0)} ∀m1 (m1 < m → ¬(x|m1 ∧y|m1 ))}. Verique (jus-
ticando) se a relação f é uma função de A em B
é uma função. Encontre os valores f (−1), f (0), ou não. Caso sim calcule o valor de f no ponto
f (2). (6, 8).
63
12. Sejam A = B = N ∪ {0} e seja a ≡ b (mod m) 3. Seja f : A → A, A = R r {1},
signica que a − b é múltiplo de m. Consideremos
a relação f ⊂ A × B denida por f = {(x, y) : x ≡ f (x) = (x + 1)/(x − 1).
y (mod 3) ∧ y ∈ {0, 1, 2}}. Verique (justicando)
se a relação f é uma função de A em B ou não. (a) Mostre que f é bijectiva.
Caso sim calcule o valor de f no ponto 5. (b) Mostre que f ◦ f = iA .
64
(i) f (x) = 2x2 e g(x) = −πx + 8 5. Seja dada a função f : [0, 9] → R denida por
(j) f (x) = (x + 1) e g(x) = −2x + 3
4 f (x) = x2 + 1. Ache f ([1, 2]) e f −1 ([−1, 5[).
(k) f (x) = |x| e g(x) = x + π 6. Seja dada a função f : [0, 9] → R denida por
p
(l) f (x) = 1
e g(x) = 1 − x 7 f (x) = x − 1. Ache f ([0, 2]) e f −1 ([−1, ∞[).
x2 +1
(m) f (x) = 3x − 5 e g(x) = |x| − 5 7. Seja dada a função f : R → R denida por f (x) =
2 sin x. Ache f ([0, π]) e f −1 (] − ∞, 0[).
(n) f (x) = e−x e g(x) = 1 − 2x
(o) f (x) = 5 sin(x + 1) e g(x) = (x + 2)5 8. Seja dada a função f : [−9, 9] → R denida por
f (x) = |x| − 1. Ache f (] − 1, 0]) e f −1 ([0, 2[).
(p) f (x) = x2 − 2x + 1 e g(x) = −2x + 1
(q) f (x) = ln(x2 + 1) e g(x) = x3 + 1 9. Seja dada a função f : [0, 9] → R denida por
f (x) = (x + 1)2 . Ache f ([2, 3]) e f −1 ([1, ∞[).
11. Responda as perguntas 1)-4) para funções f e g
denidas pelas expressões nas alíneas do exercício 10. Seja dada a função f : R → R denida por f (x) =
anterior, mas agora f e g são consideradas como 3x. Ache f (]1, 2[) e f −1 (R r {1}).
funções de [1, 2] em R. Que alíneas têm conclu- 11. Seja dada a função f : [0, 9] → R denida por
sões diferentes das conclusões correspondentes do f (x) = x3 + 1. Ache f ([3, 4]) e f −1 (R r {0}).
exercícios anterior?
12. Seja dada a função f : R → R denida por f (x) =
11.6.3 Exercícios (secção 11.5) 2x . Ache f (]0, 1]) e f −1 (]0, ∞[).
1. Seja X = {1, 2, 3, 4, 5} e a função f : X → X 13. Seja dada a função f :]0, ∞[→ R denida por
denida pela tabela. Determine a imagem do con- f (x) = ln x. Ache f ([1, ∞[) e f −1 (] − ∞, 1]).
junto A pela função f e a preimagem de A pela 14. Seja dada a função f : R r {0} → R denida por
função f . f (x) = x1 . Ache f (]0, 1]) e f −1 (] − 1, 0[).
x 1 2 3 4 5 15. Seja dada a função f : R r {0} → R denida por
(a) , A = {2, 3}.
f (x) 4 2 3 2 4 f (x) = − x1 . Ache f (]0, 1]) e f −1 (]0, ∞[).
x 1 2 3 4 5 16. Seja dada a função f : [0, 9] → R denida por
(b) , A = {1, 3, 5}.
f (x) 1 1 3 3 4 f (x) = 5. Ache f ([1, 2]) e f −1 ([−1, 5]).
x 1 2 3 4 5
(c) , A = {1, 4}. 17. Seja dada a função f : [−9, 9] → R denida por
f (x) 5 4 3 2 1
f (x) = x2 . Ache f (] − 9, 9[r[0, 1]) e f −1 ({−9, 4}).
x 1 2 3 4 5
(d) , A = {1, 2, 3, 5}. 18. Seja dada a função f : [0, ∞[→ R denida por
f (x) 2 3 3 4 5
f (x) = −x + 2. Ache f ([1, ∞]) e f −1 ({0, 1}).
x 1 2 3 4 5
(e) , A = {3, 5}. 19. Seja dada a função f : R → R denida por f (x) =
f (x) 1 2 3 3 3
− cos x. Ache f ([9, ∞[) e f −1 ({−1, 0, 1}).
x 1 2 3 4 5
(f) , A = {4}. 20. Seja dada a função f : R → R denida por f (x) =
f (x) 4 2 4 1 3
arctan x. Ache f ([0, 1[) e f −1 ([−1, ∞[).
x 1 2 3 4 5
(g) , A = {2, 3}. 21. Seja dada a função f : [0, 9] → R denida por
f (x) 4 4 4 4 4
f (x) = |x − 5|. Ache f ([5, 9]) e f −1 ([−2, 2[).
x 1 2 3 4 5
(h) , A = {2, 3, 5}.
f (x) 3 3 3 4 4 22. Demonstrar que se X1 ⊂ X2 então
x 1 2 3 4 5 f (X1 ) ⊂ f (X2 ).
(i) , A = {1, 5}.
f (x) 5 3 3 3 3
A proposição reciproca é verdadeira?
2. Sobre o conjunto U = {0, 1, 2, 3, 4, 5} é denida
a função f : U → U segundo a formula f (x) = 23. Seja f : A → B . Demonstrar que ∀X ⊂ A
x2 mod 6. Encontrar as imagens e pré-imagens X ⊂ f −1 (f (X)).
f (U ), f −1 (U ), f (B), f −1 (B) onde B = {2, 3, 5}.
Resolver a equação f (x) = x. Construir um exemplo com X 6= f −1 (f (X)) Indi-
cação. Sejam
3. Sejam A = {0, 1, 2, 3, 4, 5, 6, 7} e f : A → A a fun-
ção denida pela fórmula f (x) = x2 mod 8. Achar A = {a, b, c, d}, B = {1, 2, 3, 4}.
um elemento x ∈ f (A) tal que x ∈ / f −1 ({x}).
Pode ser considerada a função f : A → B ,
4. Seja f : A → R onde A = R r {0} a função de-
nida por f (x) = x + 1/x. Achar f ([2, 3]), f (A), x a b c d
f −1 ([0, +∞)). f (x) 2 4 2 1
65
24. Seja f : A → B , Y1 , Y2 ⊂ B , Y1 ⊂ Y2 . Demonstrar (p) Se f : X → Y é uma função e A, B ⊂ Y ,
que se f −1 (Y1 ) = f −1 (Y2 ) então então f −1 (A ∩ B) = f −1 (A) ∩ f −1 (B).
(q) Se f : X → Y é uma função e A, B ⊂ X ,
(Y2 r Y1 ) ∩ f (A) = ∅.
então f (A ∩ B) ⊂ f (A) ∩ f (B).
25. Demonstrar as seguintes propriedades da opera- (r) Se f : X → Y é uma função e A, B ⊂ Y ,
ção pré-imagem (directamente, não citando ao te- então f −1 (A ∪ B) = f −1 (A) ∪ f −1 (B).
orema 11.9): (s) Se f : X → Y é uma função e A, B ⊂ X ,
então f (A ∪ B) = f (A) ∪ f (B).
(a) f −1
(X ∪ Y ) = f −1
(X) ∪ f −1
(Y )
(b) f −1
(X ∩ Y ) = f −1
(X) ∩ f −1
(Y ) Sugestão: F,F,V,F,V,V,V,V,F,V,F,V,V,F,V,V,V,V,V.
c
(c) f −1 c
(X ) = f −1
(X)
26. Sejam f : A → B, X ⊂ A, Y ⊂ B . Demonstrar
que
X ⊂ f −1 (Y ) ⇔ f (X) ⊂ Y.
66
Tema IV
67
Nguyen Cong Hoan, DMI.UEM.2013 Lição 10. Conjuntos Enumeráveis. LTC 79
Lição 10 Capítulo 4
Definição 4.1 Um conjunto X é infinito quando possui um subconjunto próprio X0, X0⊊X, tal que
existe uma correspondência um-a-um entre X e X0 . Um conjunto é finito se não for infinito.
Observação 4.1. Em outras palavras, um conjunto X é infinito se e somente se existe uma injecção
f : X → X tal que f(X) é um subconjunto próprio de X, f(X)=X0 ⊊ X.
Logo, o conjunto N de números naturais é um conjunto infinito tomando f(n) = 2n, f(N)=Np⊊N.
Exemplo 4.1 O conjunto Ø e os conjuntos unitários (Um conjunto unitário é um conjunto que consiste
de um único elemento) são finitos.
Resolução. Como o conjunto vazio não possui nenhum subconjunto próprio, o conjunto vazio é finito.
Seja {a} um conjunto unitário qualquer. Como o único subconjunto próprio de {a} é o conjunto vazio,
e não há nenhuma correspondência biunívoca entre {a} e Ø, {a} é necessariamente finito.
Teorema 4.1
(a) Todo superconjunto, de um conjunto infinito, é infinito.
(b) Todo subconjunto, de um conjunto finito, é finito.
Demonstração.
(a) Seja X um conjunto infinito e seja Z um superconjunto de X e Z ≠ X, i.e., X ⊊ Z . Então, pela
Definição 4.1 (Observação 1), existe uma injecção f : X → X tal que f(X) ≠ X, f(X)=X0 ⊊ X.
f ( y ) se y ∈ X
Defina uma função g : Z → Z por g(z) =
z se z ∈ Z − X
Deixamos ao leitor verificar que a função g : Z → Z é injectora e que g(Z ) ≠ Z .
Nguyen Cong Hoan, DMI.UEM.2013 Lição 10. Conjuntos Enumeráveis. LTC 80
Demonstração. Como X é infinito, pela Definição 4.1, existe uma injecção f : X → X tal que f(X) ≠ X,
f(X)=X0 ⊊ X. Como g : X → Y é uma correspondência um-a-um, também o é g -1 : Y → X (Teorema
3.14, Capítulo 3). Temos agora o seguinte diagrama de injecções:
g
X → Y
f↑ ↑h
X ← Y
g-1
Demonstração. Pela Definição 4.1, existe uma injecção f : X → X tal que f(X) ⊊ X .
Há todos dois casos a serem considerados: (1) x0 ∈ f(X), ou (2) x0 ∈ X - f(X).
Em cada caso, devemos construir uma injecção g : X- {x0} → X- {x0}, tal que g(X- {x0}) ≠ (X- {x0}).
Caso 1. x0 ∈ f(X).
Existe um elemento x1 em X tal que f(x1) = x0. Uma função g : X- {x0}→ X- {x0} pode agora ser
definida por
f ( x) se x ≠ x1
g(x) =
x2 se x = x1 ∈ X − {x0 }
em que x2 é um elemento do conjunto não vazio X - f(X), arbitrariamente fixado.
Segue que g : X- {x0} → X- {x0} é injectora e que g(X- {x0}) = f(X- {x0 ; x1 }) ∪ {x2} ≠ X- {x0}
Portanto, X- {x0} é infinito neste caso.
Caso 2. x0 ∈ X - f(X).
Defina a função
g : X- {x0}→ X- {x0} por g(x) = f(x) para todo x ∈ X- {x0}.
Como f : X → X é injectora, também o é g : X- {x0} → X- {x0}. Finalmente,
g(X- {x0}) = f(X) – {f(x0)} ≠ X- {x0}
Portanto, em qualquer caso, X- {x0} é infinito. □
Nguyen Cong Hoan, DMI.UEM.2013 Lição 10. Conjuntos Enumeráveis. LTC 81
Denotação. No que segue, denotaremos por Nk, k ∈N, o conjunto de todos os números naturais de 1 até
k; isto é, Nk = {1; 2; ... ;k}.
Como uma aplicação do Teorema 4.3, mostramos no seguinte exemplo que cada Nk é finito.
Demonstração.
Condição suficiente: Se X é vazio ou está em correspondência um-a-um com algum Nk, então, pelo
Corolário do Teorema 4.2, e Exemplos 4.1 e 4.2, o conjunto X é finito.
Condição necessária: Para mostrar a recíproca, mostramos, equivalentemente, sua contrapositiva:
Se X ≠ Ø e X não está em correspondência um-a-um com nenhum Nk, então X é infinito.
Podemos tomar um elemento x1 de X, e ter novamente X – {x1} não vazio; pois, caso contrário,
teríamos X = {x1} em correspondência com N1, uma contradição com a hipótese sobre X.
Continuando desta maneira, suponhamos que escolhemos elementos x1, x2..., xk de X. Então X – { x1,
x2..., xk } não vazio; caso contrário, teremos X = { x1, x2..., xk } em correspondência um-a-um com Nk,
uma contradição com nossa hipótese sobre X.
Logo, podemos sempre escolher um elemento xk+1 de X – {x1, x2..., xk}.
Então, por indução matemática, para todo número natural n, existe um subconjunto próprio {x1, x2...,
xk} de X. Denotemos o conjunto dos xn's escolhidos por Y . Então a função
f : Y → Y – {x1}, definida por f(xk) = xk+1 para todo k ∈ N,
estabelece uma correspondência um-a-um entre Y e seu subconjunto próprio Y- {x1}. Portanto, pela
Definição 4.1, Y é infinito e portanto, pelo Teorema 4.1, X é infinito. □
Observação 4.2. Mencionaremos aqui que o Teorema 4.4 sugere uma definição alternativa de
conjuntos finitos e infinitos. Podemos definir um conjunto como sendo finito se e somente se ele é vazio
ou está em correspondência um-a-um com algum Nk, e sendo infinito se e somente se não é finito. Desta
definição alternativa, nossa Definição 4.1 pode ser demonstrada como um teorema. Entretanto, isto
requereria mais ou menos o mesmo montante de trabalho requerido pela nossa presente abordagem.
Exercícios 4.1
1. Complete a demonstração do Teorema 1.
2. Seja g : X → Y uma correspondência um-a-um. Demonstre que se X é finito, então Y é finito.
3. Demonstre que os conjuntos R, Q e Z são infinitos.
4. Demonstre que se A é um conjunto infinito, então A × A também o é.
5. Demonstre que se A e B são conjuntos infinitos, então A ∪ B é um conjunto infinito.
Nguyen Cong Hoan, DMI.UEM.2013 Lição 10. Conjuntos Enumeráveis. LTC 82
Definição 4.2 Dois conjuntos X e Y dizem-se equipotentes, facto denotado por X ~ Y ou seja cardX =
cardY, quando existe uma correspondência um-a-um f : X → Y .
Usando esta notação conveniente, a primeira metade do Problema 9, Exercícios 3.7 pode ser
reenunciado como: Se f : X ↝ Y e g : Y ↝ Z, então g o f : X ↝ Z.
Teorema 4.5 Seja Ω um conjunto de subconjuntos de um universo U e seja R uma relação em Ω dada
por: XRY se e somente se X e Y são membros de Ω e X ~ Y . Então R é uma relação de equivalência
em Ω.
(X,Y) ∈ R ⇔ X ∈ Ω ∧ Y ∈ Ω ∧ (X ~ Y)
Demonstração. Exercício.
No seguinte exemplo, os símbolos ]0; 1[ e ] -1; 1[ denotam intervalos (abertos) de números reais.
Exemplo 4.3
(a) ]0; 1[ ~ ] -1; 1[.
(b) ] -1; 1[ ~ R, e R ~ ]0; 1[.
Resolução. (a) A função f: ]0; 1[ → ] -1; 1[, dada por f(x) = 2x - 1, é uma correspondência um-a-um.
Portanto, ]0; 1[ ~ ] -1; 1[.
πx
(b) A função trigonométrica g: ] -1; 1[ → R, dada por g(x) = tg( ), é uma correspondência um-a-um;
2
portanto ] -1; 1[ ~ R. (?)
Nguyen Cong Hoan, DMI.UEM.2013 Lição 10. Conjuntos Enumeráveis. LTC 83
πx
(?) O leitor deveria verificar esta Asserção em (b) esboçando um gráfico de g(x) = tg( ).
2
Uma demonstração rigorosa pode ser obtida verificando-se as seguintes duas observações:
(i) g: ]-1; 1[ → R é contínua, e ilimitada, tanto superiormente como inferiormente.
π πx
(ii) g’(x) = ( ) sec2( ) > 0, ∀ x, então g é estritamente crescente.
2 2
Como a “relação" de equipotência é transitiva, ]0; 1[ ~ ] -1; 1[ e ] -1; 1[ ~ R implicam ]0; 1[ ~ R.
xn k ∈ Y – { x n1; x n 2 ; ... ; xn k −1 }.
Um tal nk sempre existe pois Y é infinito, o que garante que Y – { x n 1 ; x n 2 ; ... ; xn k −1 } ≠ Ø para cada
k ∈ N. Além disso, este algoritmo esgota todos os elementos de Y.
Deste modo, construímos uma correspondência um-a-um f : Y ↝ N, sendo f(k) = xn k para cada k ∈ N.
Portanto, Y é enumerável. □
Uma demonstração mais curta, porém menos intuitiva, do Teorema 4.8, é indicada no Problema 10 ao
final desta secção.
O seguinte corolário é uma consequência imediata da Definição 4.3 e do Teorema 4.8.
Exercícios 4.2
1. Complete a demonstração do Teorema 6.
2. Complete a demonstração do Teorema 7.
3. Demonstre que se X e Y são dois conjuntos, então X × Y ~ Y × X.
4. Demonstre que se (X - Y ) ~ (Y - X) então X ~ Y .
5. Demonstre a seguinte generalização do Teorema 4.6: Seja { Aγ : γ ∈ Γ } e { Bγ : γ ∈ Γ } duas
famílias de conjuntos disjuntos, tal que Aγ ~ Bγ para cada γ ∈ Γ . Então, U Aγ ~ U Bγ .
γ ∈Γ γ ∈Γ
Consequentemente, pelo Teorema 4.6, temos (A ∪ B) ~ (Np ∪ Ni) = N, o que demonstra que
A ∪ B é enumerável.
Caso 2. A ∩ B ≠ Ø.
Seja C = B - A. Então A ∪ C = A ∪ B e A ∩ C = Ø; o conjunto C ⊂ B é ou finito ou
enumerável [Corolário 4.2 do Teorema 4.8]. Se C é finito, pelo Problema 7 dos Exercícios 4.2,
A ∪ C é enumerável, e se C é enumerável, então A ∪ C é enumerável, pelo caso 1 acima.
Portanto, o conjunto A ∪ B é enumerável. □
n
Corolário 4.3 Sejam A1;A2; ... ;An conjuntos enumeráveis. Então UA i é enumerável.
i =1
Demonstração. Considere a função f : N × N → N dada por f(j; k) = 2j3k para todo (j; k) ∈ N × N.
Esta função é injectora, de modo que
N × N ~ f(N × N) ⊂ N:
Como N × N é infinito, f(N × N) também o é. Pelo Teorema 4.8, f(N × N) é enumerável e portanto N
× N é enumerável. □
Corolário 4.4 Para cada k ∈ N, seja Ak um conjunto enumerável satisfazendo Aj ∩ Ak = Ø para todo j
+∞
≠ k. Então UA k = U Ak é enumerável.
k =1 k∈N
Nota. Este resultado é verdadeiro sem a hipótese “Aj ∩ Ak = Ø para todo j ≠ k." Veja Problema 7.
Demonstração. Para cada k ∈ N, seja fk : N → N × {k} uma função ao dada por fk(j) = (j; k) para todo
j ∈ N. Claramente, cada fk : N → N × {k} é uma correspondência um-a-um. Ou seja, N ~ N × {k}.
Como Ak ~ N e N ~ N × {k} para cada k ∈ N, temos Ak ~ N × {k} para cada k ∈ N. Segue então, do
Problema 5 dos Exercícios 4.2, que
U Ak ~ U N × {k}.
k∈N k∈N
Mas o conjunto
U
k∈N
N × {k} = N × N
Demonstração. Representaremos cada número racional de maneira única como p/q, sendo p ∈ Z, q ∈
N* e o máximo divisor comum de p e q igual a 1. Seja Q+ o conjunto de tais elementos com p/q > 0, e
seja Q– = { – p/q : p/q ∈ Q+}.
Então Q = Q+ ∪ {0} ∪ Q– . É evidente que Q+ ~ Q– . Portanto, para mostrar que Q é enumerável, é
suficiente mostrar que Q+ é enumerável. Para este propósito, consideramos a função f : Q+ → N × N,
Nguyen Cong Hoan, DMI.UEM.2013 Lição 10. Conjuntos Enumeráveis. LTC 86
dada por f(p/q) = (p; q). Como esta função é injectora, temos Q+ ~ f(Q+) ⊂ N × N. Como Q+, como um
superconjunto de N, é infinito, f(Q+) é um subconjunto infinito do conjunto enumerável N × N.
Portanto, f(Q+) é enumerável e consequentemente Q+ é enumerável. □
O próximo teorema indica que os conjunto enumeráveis são, em um certo sentido, os menores em
“tamanho" dentre os conjuntos infinitos.
Demonstração. Seja X um conjunto infinito qualquer. Então X ≠ Ø, de modo que podemos escolher
um elemento, digamos x1, no conjunto X. A seguir, seja x2 um elemento em Y – {x1 }. De modo
semelhante, escolha um elemento x3 do conjunto não vazio X - {x1; x2 }. Tendo assim definido xk-1,
escolhemos um elemento xk no conjunto X - {x1; x2; ... ; xk-1 }. Tal xk existe para cada k ∈ N, porque X
é infinito, o que garante que X - {x1; x2; ... ; xk-1 } ≠ Ø para todo k ∈ N.
O conjunto {xk : k ∈ N} é um subconjunto enumerável de X, e a demonstração está completa. □
Exercícios 4.3
1. Demonstre a asserção do Exemplo 4.3: O conjunto Z de todos os inteiros é enumerável.
2. Demonstre o Corolário 4.3 do Teorema 4.9.
3. Demonstre que a união de um número finito de conjuntos contáveis é contável.
4. Demonstre que se A e B são conjuntos enumeráveis, então também o é A × B.
Em particular, Z × N, Z × Z, e Q × Q são enumeráveis.
5. Encontre uma função injectora f : Q → Z × N e dê uma demonstração alternativa para o Exemplo
4.5.
6. Demonstre que o conjunto dos círculos no plano cartesiano, tendo raios racionais e centros em
pontos com ambas as coordenadas racionais, é enumerável.
7. Demonstre que se para cada k ∈ N, Bk é um conjunto enumerável, então U Bk é enumerável.
k∈N
Teorema 4.12 O intervalo aberto ]0; 1[ de números reais é um conjunto não enumerável.
Demonstração. Expressemos primeiramente cada número x, x < 0 < 1, como uma expansão decimal na
forma 0,x1x2x3 ... , com xn ∈ {0; 1; 2; ... ; 9} para cada n.
Por exemplo, 1/3 = 0,333..., 2 /2 = 0,707106... . De modo a ter uma única expressão, para aqueles
números com uma expansão decimal finita, tais como 1/4 = 0,25, concordaremos em subtrair 1 do
último dígito e acrescentar 9's, de modo que
1/4 = 0,24999... , e não 0,25000... .
Sob este acordo, dois números no intervalo ]0; 1[ são iguais se e somente se os dígitos correspondentes,
de suas expansões decimais, são idênticos. Assim, se dois tais números, x = 0,x1x2x3 ... e y = 0,y1y2y3 ...
tem uma casa decimal, digamos a k-ésima casa decimal, tal que xk ≠ yk, então x ≠ y.
Nguyen Cong Hoan, DMI.UEM.2013 Lição 10. Conjuntos Enumeráveis. LTC 87
Demonstração. Fizemos a demonstração, no Exemplo 4.3(b), de que R ~ ]0; 1[. Agora, ]0; 1[ é não
enumerável; portanto seu conjunto equipotente R também é não enumerável. (veja Problema 1). □
Exemplo 4.6 O conjunto de todos os números irracionais é não enumerável.
(2) A existência de conjuntos não enumeráveis mostra que existem classes de conjunto infinitos.
Na verdade, como o leitor verá no próximo capítulo, existe uma abundância de “classes de
equipotência" de conjunto infinitos.
Exercícios 4.4
1. Sejam A e B dois conjuntos equipotentes. Demonstre que se A é não enumerável, então B é não
enumerável.
2. Demonstre que todo superconjunto de um conjunto não enumerável é não enumerável.
3. Usando o resultado do Problema 2, acima, dê uma demonstração alternativa do corolário do Teorema
4.12.
4. Demonstre que o conjunto dos números irracionais entre 0 e 1 é não enumerável.