Apostila de Elementos da Matemática

Apostila de Elementos da Matemática

(Parte 1 de 3)

Universidade de Sao Paulo Instituto de Ciencias Matematicas e de Computacao

SMA 341 - Elementos de Matemática Notas de Aulas

Ires Dias Sandra Maria Semensato de Godoy

Sumário

1.1 Proposicoes e Conectivos Logicos7
1.2 Proposicoes Compostas e Tabelas-verdade9
1.3 Tautologia e Equivalencia Logica12
1.4 Teoremas15
1.5 Definicao de =⇒ e ⇐⇒15
1.6 Quantificadores18
1.7 Metodo Dedutivo21
1.8 Metodos de Demonstracao2
1.9 Exercıcios24

1 Nocoes de Logica 7 2 Teoria dos Conjuntos 27

2.1 Nocoes Primitivas, Definicoes e Axiomas27
2.2 Operacoes com Conjuntos34
2.3 O Produto Cartesiano de Dois Conjuntos40
2.4 Exercıcios42

3 Relacoes 45

3.1 Definicoes e Exemplos45
3.2 Relacoes de Equivalencias e Particoes49
3.3 Relacoes de Ordem53
3.4 Funcoes57
3.5 Exercıcios57

4 Sumario 4 Nocoes de Cardinalidade 63

4.1 Conjuntos Equipotentes, Enumeraveis e Contaveis63
4.2 Numeros Cardinais e a Hipotese do Contınuo68
4.3 Cardinal de um conjunto - Teorema de Cantor70
4.4 Aritmetica Cardinal71
4.4.1 Adicao de Numeros Cardinais71
4.4.2 Multiplicacao de Numeros Cardinais72
4.4.3 Potencias de Numeros Cardinais73
4.5 Exercıcios75

5 Os Numeros Naturais 79

5.1 Os Axiomas de Peano79
5.2 Adicao em N81
5.3 Multiplicacao em N83
5.4 Relacao de Ordem em N85
5.5 Exercıcios89

6 Os Numeros Inteiros 91

6.1 A adicao em Z92
6.2 A multiplicacao em Z94
6.3 Relacao de Ordem em Z96
6.4 A Imersao de N em Z97
6.5 Valor Absoluto98
6.6 Aritmetica em Z100
6.6.1 Multiplos e Divisores100
6.6.2 Algoritmo da divisao ou algoritmo de Euclides101
6.6.3 Maximo Divisor Comum102
6.6.4 Mınimo Multiplo Comum108
6.7 Numeros Primos110
6.8 Congruencias e Aplicacoes112
6.8.2 A validade de um numero de CPF118
6.8.3 Em que dia da semana voce nasceu?119
6.9 Exercıcios121
7.1 A adicao em Q126
7.2 A Multiplicacao em Q127
7.3 A Divisao em Q128
7.4 Relacao de Ordem em Q129
7.5 Exercıcios130

Referencias Bibliograficas 133

1 Noções de Lógica

“Logica e a higiene usada pelos matematicos para conservar suas ideias saudaveis e fortes”. Herman Weyl (1885-1955)

1.1 Proposições e Conectivos Lógicos

O estudo da logica e o estudo dos princıpios e metodos utilizados para distinguir argumentos validos daqueles que nao sao validos.

O principal objetivo desta secao e ajudar o aluno a entender os princıpios e metodos usados em cada etapa de uma demonstracao. Sem alguns conceitos logicos basicos, e impossıvel escrever e/ou entender uma demonstracao. Quando demonstramos um teorema, estamos demonstrando a veracidade de certas declaracoes. Em geral estas declaracoes sao compostas de proposicoes, quantificadores, conectivos e/ou modificadores.

O ponto inicial da logica e o termo“proposicao” usado em um sentido tecnico. Por uma proposicao entendemos uma sentenca declarativa (afirmativa) ou uma afirmacao verbal que e verdadeira ou falsa, mas nao ambas simultaneamente. A designacao Verdadeira (V) ou Falsa (F) de uma proposicao e dita ser seu valor verdade ou seu valor logico.

Exemplo 1.1. As seguintes afirmacoes sao proposicoes:

(b) 6 e um numero primo.

(c) Pedro tem olhos azuis.

(d) O dia 10 de agosto de 1935 foi uma quarta-feira.

(e) O 1000o digito da expansao decimal de √ 2 e 6.

(f) Existe vida inteligente em Marte.

Note que (a) e claramente V; (b) e claramente F; (c) e uma proposicao pois e V ou

F, mesmo que eu nao conheca o Pedro; (d) e V ou F, mesmo que seja difıcil saber a resposta; o mesmo vale para (e) e (f).

Exemplo 1.2. As seguintes afirmacoes nao sao proposicoes:

(b) AH! se eu passar em Elementos!

(f) Esta proposicao e falsa.

(g) Hoje e terca-feira.

(h) Esta chovendo.

Note que (a) e interrogativa e nao declarativa; (b) e exclamativa e nao declarativa; (c) e uma sentenca aberta, pode ser V ou F dependendo da variavel x; (d) nao e V ou F, pois nao existe ordem em C; (e) nao e uma proposicao, o que seria proposicao e “para todo x ∈ R, x(x + 4) = x2 + 4x”; (f) e um paradoxo, viola a definicao de proposicao pois e V e F ao mesmo tempo; (g) e uma sentenca aberta que depende da variavel “hoje” assim como (h) depende da variavel “tempo”.

1.2. Proposicoes Compostas e Tabelas-verdade 9

1.2 Proposições Compostas e Tabelas-verdade

As proposicoes do exemplo 1.1 sao todas proposicoes simples, ou seja, nao foram obtidas por combinacoes ou composicoes de outras proposicoes. A combinacao ou coneccao de duas ou mais proposicoes simples e uma proposicao composta. Ha varias maneiras de conectar proposicoes, somente cinco sao frequentemente usadas. Sao os conectivos:

(a) “nao”, simbolizado por ∼, tambem chamado de modificador. (b) “e”, simbolizado por ∧ (operacao de conjuncao). (c) “ou”, simbolizado por ∨ (operacao de disjuncao). (d) “se · entao ·”, simbolizado por −→ (conectivo condicional). (e) “· se, e somente se ·”, simbolizado por ←→ (conectivo bicondicional).

Como em algebra usamos letras para representar numeros, em logica usaremos letras minusculas para representar proposicoes.

Definição 1.3. Para proposicoes p e q, definimos:

(a) A negacao de p, denotada por ∼ p, lida “nao p”, como sendo a proposicao com valor verdade diferente do de p.

(b) A conjuncao de p e q, denotada por p ∧ q, lida “p e q”, como sendo a proposicao que e verdadeira somente quando p e q sao ambas verdadeiras.

(c) A disjuncao de p e q, denotada por p ∨ q, lida “p ou q”, como sendo a proposicao que e falsa somente quando p e q sao ambas falsas.

(d) A condicional de p e q, denotada por p −→ q, lida“se p, entao q”ou“p implica q” ou “p condiciona q” ou “p e condicao suficiente para q”, como sendo a proposicao que assume o valor falso somente quando p for verdadeira e q for falsa.

(e) A bicondicional de p e q, denotada por p ←→ q, lida “p se, e somente se q” ou “p bicondiciona q” ou “p e condicao necessaria e suficiente para q”, como sendo a proposicao que assume o valor verdadeiro somente quando p e q sao ambas verdadeiras ou p e q sao ambas falsas.

Exemplo 1.4. “Maria tem uma caneta”: e uma proposicao p. “O sol e uma estrela”: e uma proposicao q. Podemos formar as novas proposicoes:

- Maria tem uma caneta e o sol e uma estrela. (p ∧ q)

- Maria tem uma caneta ou o sol e uma estrela. (p ∨ q)

- Se Maria tem uma caneta, entao o sol e uma estrela. (p −→ q)

- Maria tem uma caneta se, e somente se o sol e uma estrela. (p ←→ q)

- Nao e verdade que Maria tem uma caneta. (∼ p)

Observação 1.5. As definicoes sao condicoes necessarias e suficientes e, portanto, sao equivalentes a condicoes que tem o conectivo “se, e somente se”.

Para expressarmos os valores logicos de uma proposicao composta e muito conveniente utilizarmos uma tabela, chamada tabela-verdade da proposicao, onde cada linha expressa os valores-verdade da composta, obtidos a partir dos valores-verdade das proposicoes dadas e dos conectivos usados. Vejamos as tabelas-verdade das proposicoes definidas acima:

p q p ∧ q p q p ∨ q

Tabela 1.1: Tabelas-verdade da definicao 1.3.

1.2. Proposicoes Compostas e Tabelas-verdade 1

A partir destas cinco tabelas-verdade, podemos construir uma tabela-verdade para qualquer proposicao composta. Atraves de exemplos apresentaremos duas maneiras de fazermos isso.

Exemplo 1.6. Construa a tabela-verdade para a proposicao ∼ [(∼ p) ∧ (∼ q)].

Tabela 1.2: Construcao da tabela-verdade do exemplo 1.6.

Esta tabela representa como chegar na proposicao ∼ [(∼ p) ∧ (∼ q)] passo a passo. Na realidade a tabela-verdade desta proposicao e:

Tabela 1.3: Tabela-verdade do exemplo 1.6.

Vale observar que:

1. O conectivo ∼ abrange somente a primeira expressao que o segue, exceto quando se utiliza parenteses e/ou colchetes

3. O numero de linhas de uma tabela-verdade de uma proposicao e dado por 2n, onde n e o numero de proposicoes simples que a compoem.

Exemplo 1.7. Determine se a proposicao seguinte e verdadeira:

“Ou ∫ pi

−pi

∫ pi

Sejam p a proposicao ∫ pi

−pi senxdx = 0, q a proposicao d

Como o conectivo principal e “ou · ou ·”, temos que a proposicao dada e (∼ p ∧ q) ∨ (p ∧ r). Vamos entao construir a tabela-verdade desta proposicao. Para tanto, notamos que, neste caso, temos 3 proposicoes simples p,q e r. Logo, nossa tabela tera 23 = 8 linhas.

Tabela 1.4: Tabela-verdade do exemplo 1.7.

Note que p e V pois ∫ pi

−pi senxdx = 0, desde que seno e uma funcaoımpar; q e F pois

p, q e r satisfazem as condicoes da linha 4 da tabela e, assim, a proposicao dada e Falsa.

1.3 Tautologia e Equivalência Lógica

Definição 1.8. Uma proposicao que e verdadeira em todas as possibilidades logicas e dita ser uma tautologia. Se ela for falsa para todas as possibilidades logicas, ela e dita ser uma contradicao.

Note que se p e uma tautologia, entao ∼ p e uma contradicao e vice-versa.

1.3. Tautologia e Equivalencia Logica 13

Exemplo 1.9. Para toda proposicao p, a proposicao p∨ ∼ p e uma tautologia e p∧ ∼ p e uma contradicao. De fato, basta observar sua tabela-verdade.

Tabela 1.5: Tabela-verdade do exemplo 1.9.

Definição 1.10. Duas proposicoes sao ditas logicamente equivalentes se elas tiverem a mesma tabela-verdade, ou seja, se elas tem o mesmo valor verdade para cada uma das possibilidade logicas.

Exemplo 1.1. As proposicoes ∼ (p ∨ q) e ∼ p∧ ∼ q sao logicamente equivalentes. De fato, basta verificar na tabela-verdade:

Tabela 1.6: Tabela-verdade do exemplo 1.1.

O que significa a equivalencia logica deste exemplo? Por exemplo, se uma pessoa afirmar que:

e outra pessoa afirmar que:

Nao e verdade que ou lim x→0 x2 = 0 ou

temos que as duas pessoas estarao dizendo a mesma coisa, ou seja, ambas estarao certas ou ambas estarao erradas. Neste caso, como limx→0 x2 = 0 e ∫ 1 0 ex dx 6= e, temos que ambas estarao erradas (basta ver a linha 2 da tabela anterior).

Note que se duas proposicoes p e q sao logicamente equivalentes, entao p ←→ q e uma tautologia e, reciprocamente, se p ←→ q for uma tautologia, entao p e q serao logicamente equivalentes.

Em Matematica, a principal importancia das equivalencias logicas esta na ideia que duas proposicoes logicamente equivalentes podem ser vistas como a “mesma” do ponto de vista logico. Por exemplo, se duas proposicoes p e q sao logicamente equivalentes e, necessitamos demonstrar p e encontramos uma maneira mais simples ou mais facil de demonstrarmos q, entao podemos demonstrar p provando q.

Exemplo 1.12. A proposicao p −→ q e logicamente equivalente a ∼ q −→∼ p mas nao e logicamente equivalente a ∼ p −→∼ q. De fato, basta observar a tabela-verdade:

Tabela 1.7: Tabela-verdade do exemplo 1.12.

Mais ainda, a proposicao p −→ q e logicamente equivalente a ∼ (p∧ ∼ q) que e logicamente equivalente a ∼ p ∨ q, como mostra a tabela abaixo:

Definição 1.13. Se p −→ q e uma condicional, entao ∼ q −→∼ p e dita ser a condicional contra positiva, q −→ p e dita ser a condicional recıproca e ∼ p −→∼ q e a

1.4. Teoremas 15 condicional inversa.

Um teorema e uma proposicao logica que e uma tautologia. As tautologias de principal interesse em matematica sao as que envolvem os conectivos condicional e/ou bicondicional. A demonstracao de um teorema nada mais e do que a confeccao da tabela-verdade mostrando que a proposicao e de fato uma tautologia.

Em matematica usa-se outros termos como axiomas e postulados que sao fatos aceitos sem uma demonstracao; lemas e/ou proposicoes que sao teoremas cujo proposito e utiliza-los na demonstracao de outro teorema e corolarios que sao teoremas que seguem imediatamente da demonstracao de outro(s) teorema(s).

Sejam p e q proposicoes. Se p −→ q e uma tautologia, dizemos que esta proposicao condicional e uma implicacao e que p implica logicamente q e escrevemos p =⇒ q. Se p ←→ q e uma tautologia, dizemos que esta bicondicional e uma bi-implicacao e denotamos por p ⇐⇒ q. Lembre-se que p ←→ q ser tautologia significa que p e q sao logicamente equivalentes e, assim, p ⇐⇒ q representa a equivalencia entre p e q. Vamos ao nosso primeiro teorema que apresenta as propriedades basicas de =⇒.

Teorema 1.14. Sejam p,q e r proposicoes. Entao: 1. Reflexiva - p =⇒ p.

Prova: Atraves da tabela-verdade, mostraremos os ıtens 3, 6 e 14. Os outros ficam como exercıcios. Lembrando que mostrar uma implicacao =⇒ e mostrar que a condicional correspondente −→ e uma tautologia. 3. p ∧ q =⇒ p.

As correspondentes propriedades de ⇐⇒ sao apresentadas no proximo teorema.

Referentes as tautologias e as contradicoes temos:

Teorema 1.16. Sejam t uma tautologia, c uma contradicao e p uma proposicao qualquer. Entao:

Prova: Como exercıcio, fazer alguns casos.

1.6 Quantificadores

Existem sentencas para as quais nao ha como decidir se assumem valor V ou F. Por exemplo: “x + y = 5” e “Ele e jogador de futebol”. Estas sentencas sao denominadas sentencas abertas ou predicados. Podemos compor sentencas abertas usando os mesmos conectivos usados nas proposicoes e formarmos novas sentencas abertas a partir de outras mais simples.

Ha duas maneiras formais de transformar uma sentenca aberta em uma proposicao, utilizando os dois quantificadores. Para isso, necessitamos de um “universo” ou “domınio de discussao”, isto e, uma colecao de objetos para os quais consideramos propriedades. Por exemplo, na proposicao “Todos os homens sao mortais”, o universo e a colecao de todos os homens e tal proposicao pode ser escrita como “Para todo x do universo, x e mortal”.

1.6. Quantificadores 19

A frase “Para todo x do universo” e chamada um quantificador universal e e simbolizado por “∀ x”. A sentenca “x e mortal” diz alguma coisa sobre x, entao simbolizamos por p(x). Assim escrevemos “Todos os homens sao mortais” como que pode ser lida como: - para todo x, p(x);

- para cada x, p(x);

- para qualquer x, p(x).

Vejamos agora a proposicao“Alguns os homens sao mortais”. O universo e o mesmo da proposicao anterior. Com este universo em mente, podemos escrever esta proposicao como: “Existe no mınimo um homem que e mortal”; “Existe no mınimo um x, tal que x e mortal”; “Existe no mınimo um x, tal que p(x)”.

A frase “Existe no mınimo um x, tal que” e chamada quantificador existencial e denotada por “∃ x”. Usando este sımbolo, podemos escrever a proposicao “Alguns homens sao mortais” como que pode ser lida como:

- existe x, tal que p(x);

- existe ao menos um x, tal que p(x);

- para pelo menos um x, p(x).

Quando existe um unico elemento no universo que torna a proposicao (∃ x)(p(x)) verdadeira, denotamos esta proposicao por (∃! x)(p(x)) e lemos:

- existe um unico x, tal que p(x);

O conjunto dos elementos do universo que tornam uma sentenca aberta uma proposicao verdadeira e denominado conjunto-verdade. Por exemplo, para p(x) : x+1 = 5, o conjunto universo pode ser R e o conjunto-verdade e {4}, enquanto que para a sentenca aberta p(x) : sen2 x + cos2 x = 1, temos que o conjunto-verdade e igual ao conjunto universo que e igual a R.

Quando estiver subentendido quem e o conjunto universo, os quantificadores podem ser omitidos, por exemplo, escrevemos “(x + 1)(x − 1) = x2 − 1” no lugar de escrever “∀ x ∈ R, (x + 1)(x − 1) = x2 − 1”. Tambem e comum escrevermos os quantificadores depois da sentenca aberta, por exemplo, escrevemos “f(x) = 0, para todo x” no lugar de escrevermos “(∀ x)(f(x) = 0)”. Observe que claramente temos

Vamos mostrar (a) em um caso particular. Suponhamos que o conjunto universo de p(x) seja constituıdo pelos elementos a, b, c. Entao a proposicao (∀ x)(p(x)) significa:

1.7. Metodo Dedutivo 21

Os quantificadores nos dao uma ideia do que sao os exemplos e os contra-exemplos.

Quando temos uma proposicao verdadeira que contem um dos quantificadores, dar um exemplo e escolher uma variavel x para o qual ela e verdadeira, ou seja, e escolher um elemento do seu conjunto-verdade. Quando uma proposicao que contem um dos quantificadores nao e verdadeira, significa que o seu conjunto-verdade e diferente do conjunto universo. Assim, encontrar um contra-exemplo e escolher uma variavel x que nao esteja no conjunto-verdade.

1.7 Método Dedutivo

Vimos que demonstrar teoremas significa verificar que a proposicao dada e uma tautologia e, fizemos isso, construindo tabelas-verdade. Veremos agora outra maneira de verificar a validade de proposicoes. Este procedimento e chamado de metodo dedutivo e consiste na utilizacao de definicoes, de outros resultados pre-estabelecidos e das propriedades transitivas de =⇒ e ⇐⇒. Vejamos como utiliza-lo em exemplos.

Como

usando a transitividade de ⇐⇒, obtemos a equivalencia desejada.

Como

usando a transitividade de ⇐⇒, obtemos a equivalencia.

Exemplo 1.20. Considere as seguintes afirmacoes:

H1 : Tempo e dinheiro.

H2 : Vagabundo tem muito tempo. T : Vagabundo tem muito dinheiro.

A proposicao (H1 ∧ H2 =⇒ T) e um teorema? Se considerarmos p : “Ter tempo”, q : “Ter dinheiro” e r : “Ser vagabundo”, teremos

Exemplo 1.21. Considere agora as seguintes afirmacoes:

H1 : Penso, logo existo.

H2 : Pedras nao pensam. T : Pedras nao existem.

Se considerarmos p : “Pensar” e q : “Existir”, teremos que H1 : p −→ q, H2 :∼ p e

(Parte 1 de 3)

Comentários