Elemento de Logica Matematica e Teoria de Conjuntos

Elemento de Logica Matematica e Teoria de Conjuntos

(Parte 1 de 8)

Elementos de Lógica Matemática e Teoria dos Conjuntos Jaime Campos Ferreira

Uma reedição revista pelo autor dos capítulos iniciais das Lições de Análise Real

Departamento de Matemática Instituto Superior Técnico Outubro de 2001

Introducao

Alguns amigos e colegas, regentes das primeiras disciplinas de Analise Matematica no IST, aconselharam uma reedicao dos dois primeiros capıtulos do texto Licoes de Analise Real (que redigi ha mais de trinta anos), por entenderem que, nas condicoes actuais do nosso ensino, poderiam ser de alguma utilidade como introducao aos principais assuntos versados nas suas aulas. Foi esta a causa da presente publicacao. O texto foi agora submetido a uma revisao ligeira; no entanto, para os estudantes que utilizem tambem o livro Introducao a Analise Matematica, convem mencionar uma pequena diferenca: o conjunto dos numeros naturais (em ambos os trabalhos designado pela letra N) e definido nesse livro por forma a incluir o numero zero, enquanto no texto que agora se publica o nao inclui. Trata-se evidentemente de uma discrepancia em materia de natureza convencional, da qual, depois de devidamente acentuada, nao resultara decerto qualquer inconveniente para os eventuais utilizadores dos dois trabalhos.

Lisboa, Outubro de 2000,

Jaime Campos Ferreira

Uma edicao do Departamento de Matematica do Instituto Superior Tecnico. Setembro de 2001. Uma edicao do Departamento de Matematica do Instituto Superior Tecnico. Setembro de 2001.

Indice

1.1 Termos e proposicoes. Algebra proposicional5
1.2 Expressoes com variaveis8
1.3 Quantificadores10

1 Elementos de logica matematica 5

2.1 Conjuntos. Operacoes fundamentais17
2.2 Pares ordenados. Sequencias. Produto cartesiano. Relacoes21
2.3 Funcoes. Aplicacoes. Inversao. Composicao28
2.4 Relacoes de equivalencia. Relacoes de ordem34

2 Elementos de teoria dos conjuntos. 17 Indice remissivo 48

Cap tulo 1 Elementos de logica matematica

Para compreender bem as definicoes e teoremas que constituem as teorias matematicas cujo estudo vamos iniciar, e indispensavel habituarmo-nos a usar uma linguagem mais precisa e rigorosa do que a que se utiliza, em geral, na vida corrente. A aquisicao desse habito pode ser muito facilitada pelo recurso a algumas nocoes e sımbolos da Logica Matematica, dos quais indicaremos neste primeiro capıtulo, de forma muito resumida e largamente baseada na intuicao, aqueles que tem maior interesse para a sequencia do nosso curso.

Convem, no entanto, observar que a Logica Matematica tem hoje aplicacoes concretas extremamente importantes, em diversos domınios; uma das mais notaveis e, sem duvida, a sua utilizacao no planeamento dos modernos computadores electronicos.

1.1 Termos e proposi c~oes. Algebra proposicional.

A linguagem usada na Matematica, como qualquer outra linguagem, compreende designacoes (tambem chamadas nomes ou termos) e proposicoes (ou frases). As designacoes servem para indicar determinados objectos matematicos: numeros, pontos, conjuntos, funcoes, operacoes, figuras geometricas, etc.; as proposicoes exprimem afirmacoes — que podem ser verdadeiras ou falsas — a respeito dos mesmos objectos.

Como exemplos de designacoes registamos as seguintes1:

Observe-se que as duas primeiras designacoes se referem ao mesmo objecto: sao designacoes equivalentes ou sinonimas; para indicar que duas designacoes, a e b, sao equivalentes, escreve-se usualmente a = b. Como exemplos de proposicoes (as duas primeiras verdadeiras, as outras falsas)

1Designamos por N e R, respectivamente, o conjunto dos numeros naturais e o conjunto dos numeros reais.

CAPITULO 1. ELEMENTOS DE LOGICA MATEMATICA

Uma proposicao e necessariamente verdadeira ou falsa (mas nunca uma coisa e outra); na primeira hipotese, diz-se tambem por vezes que a proposicao tem o valor logico 1, na segunda que tem o valor logico 0. Os sımbolos 1 e 0 servem assim, de forma convencional, para designar respectivamente verdade e falsidade.

Duas proposicoes dizem-se equivalentes quando tem o mesmo valor logico; por exemplo, sao equivalentes as proposicoes

Para indicar que duas proposicoes — designadas, por exemplo, pelos sımbolos p e q — sao equivalentes, costuma-se escrever p ⇐⇒ q.

Dadas duas proposicoes, p e q, chama-se conjuncao ou produto logico de p e q, e designa-se por p∧q (ler “p e q”) a proposicao que consiste em afirmar simultaneamente p e q. A proposicao p ∧ q sera, portanto, verdadeira se o forem as duas proposicoes dadas e falsa quando uma destas for falsa (ou quando o forem ambas).

Por exemplo, a conjuncao das proposicoes “4 e um numero par” e “4 e um divisor de 10” equivale a afirmacao de que “4 e um numero par e um divisor de 10” e e, evidentemente, uma proposicao falsa.

Por outro lado, chama-se disjuncao ou soma logica de p e q, e designa-se por p ∨ q, (“p ou q”), a proposicao que consiste em afirmar que pelo menos uma das proposicoes dadas e verdadeira. Nestas condicoes, a proposicao p∨q so e falsa quando o forem ambas as proposicoes p e q. A disjuncao das duas proposicoes consideradas no exemplo anterior e a proposicao (verdadeira): “4 e um numero par ou e um divisor de 10”.

Nas tabelas seguintes, analogas as vulgares tabuadas das operacoes elementares estudadas na escola primaria, indicam-se os valores logicos das proposicoes p∧q e p∨q, em correspondencia com os possıveis valores logicos de p e q:

Observe-se que o valor logico de p ∧ q e o mınimo dos valores logicos das proposicoes p e q, enquanto o valor logico de p ∨ q e o maximo dos valores logicos das mesmas proposicoes (evidentemente, no caso de estas terem valores logicos iguais, entende-se por maximo e mınimo desses valores logicos o seu valor comum).

Nota. Podem definir-se de forma inteiramente analoga a conjuncao e a disjuncao no caso de serem dadas mais de duas proposicoes. Por exemplo, a conjuncao das proposicoes p, q, r,...consiste na afirmacao de que todas essas proposicoes sao verdadeiras e e portanto uma proposicao que so e falsa se alguma das proposicoes p, q, r,..., o for.

1.1. TERMOS E PROPOSIC OES. ALGEBRA PROPOSICIONAL.

PSfrag replacements p∧ q p q

PSfrag replacements p ∧ q

Sendo p uma proposicao, a negacao de p e uma nova proposicao, que costuma designar-se por ∼ p ou nao p. A proposicao ∼ p e verdadeira sse2p e falsa. A soma dos valores logicos de p e ∼ p e, portanto, sempre igual a unidade. E evidente que, para toda a proposicao p, se tem:

Verificam-se tambem sem dificuldade as seguintes propriedades (conhecidas por primeiras leis de De Morgan), que relacionam as tres operacoes logicas designadas pelos sımbolos ∨, ∧ e ∼:

Em linguagem corrente, a primeira destas propriedades poderia exprimir-se da forma seguinte: negar que as proposicoes p e q sejam ambas verdadeiras equivale a afirmar que pelo menos uma delas e falsa.

Uma outra operacao logica importante e a implicacao: dadas duas proposicoes p e q, designa-se correntemente pelo sımbolo p =⇒ q (que pode ler-se “p implica q” ou “se p, entao q”) uma nova proposicao que consiste em afirmar que, se p e verdadeira, q tambem o e. A implicacao p =⇒ q so e portanto falsa no caso de p ser verdadeira e q ser falsa, isto e, se o valor logico de p for maior do que o de q. Assim, por exemplo, das proposicoes:

2Usamos sse como abreviatura da expressao se e so se.

CAPITULO 1. ELEMENTOS DE LOGICA MATEMATICA so a primeira e falsa.

Evidentemente, quando se verificam conjuntamente as implicacoes p =⇒ q e q =⇒ p, as proposicoes p e q sao equivalentes; simbolicamente:

1.2 Express~oes com vari aveis.

Alem dos termos e proposicoes que temos estado a considerar, a linguagem matematica usa constantemente expressoes em que intervem variaveis, isto e sımbolos (em geral, letras) que podem ser substituıdos por designacoes de acordo com determinadas regras.3 Por exemplo, as expressoes:

nao sao propriamente designacoes, mas converter-se-ao em designacoes (de numeros reais) se as letras que nelas figuram forem substituıdas por numeros reais arbitarios; assim, se substituirmos x por 1 e y por 0, as tres expressoes referidas converter-se-ao em designacoes do numero 1.

As expressoes com variaveis que, como as precedentes, se transformam em designacoes quando as variaveis que nelas figuram sao substituıdas por designacoes convenientes, chamaremos expressoes designatorias . Sao tambem expressoes designatorias as seguintes:

Convem no entanto observar que, para que estas ultimas expressoes se convertam em designacoes de numeros reais, nao basta substituir as variaveis por numeros reais arbitrarios: por exemplo, da substituicao de x por 0 nao resultaria em qualquer dos casos a designacao de um numero real (fosse qual fosse o valor atribuıdo a variavel y, no caso da terceira expressao).

Duas expressoes designatorias numa mesma variavel x dizem-se equivalentes se todo o valor de x que converta alguma delas numa designacao, converter a outra numa designacao equivalente. Sao equivalentes no con- junto dos reais as expressoes x e x3, mas nao o sao as expressoes √|x|e √ x (substituindo x por −1, por exemplo, a primeira converte-se numa designacao do numero 1 e a segunda num sımbolo sem significado).

Evidentemente, a definicao de equivalencia e analoga no caso de expressoes designatorias com mais de uma variavel; assim, por exemplo, sao equivalentes as expressoes designatorias:

3Nos casos habituais uma variavel pode ser substituıda por qualquer termo de entre os que se referem aos objectos de um determinado conjunto, chamado domınio da variavel em causa. Atribuir a variavel, como valor, um certo objecto (pertencente ao domınio) consiste precisamente em substituı-la por qualquer designacao desse objecto, em todos os lugares em que ela ocorra na expressao considerada.

1.2. EXPRESSOES COM VARIAVEIS.

(supondo que x e y tem por domınio o conjunto R). Consideremos agora as expressoes:

Se em qualquer destas expressoes substituirmos todas as variaveis por designacoes de numeros reais, obteremos desta vez, nao designacoes, mas sim proposicoes, verdadeiras ou falsas.

(Parte 1 de 8)

Comentários