Estruturas Discretas – INF 1631
Thibaut Vidal
Departamento de Informática, Pontifı́cia Universidade Católica do Rio de Janeiro
Rua Marquês de São Vicente, 225 - Gávea, Rio de Janeiro - RJ, 22451-900, Brazil
[email protected]
August 10, 2015
>
Conceitos Básicos Quantificadores Exercı́cios
1/15
Conteúdo
1
Conceitos Básicos
Teorema
Lema e Corolário
Proposição
Axiomas e Definições
2
Quantificadores
3
Exercı́cios
>
Conceitos Básicos Quantificadores Exercı́cios
1/15
Conceitos Básicos
• O primeiro passo para a resolução de um problema é defini-lo
correta e precisamente. A definição do problema envolve as
seguintes questões:
I
I
I
>
Qual o objeto (ou quais os objetos) em análise?
Quais são as caracterı́sticas desse objeto (ou desses objetos)?
O que se deseja provar?
Conceitos Básicos Quantificadores Exercı́cios
2/15
Teorema
• O objeto básico de uma demonstração e a proposição que
desejamos demonstrar. Essa proposição recebe o nome de
teorema.
• Um teorema e dividido em duas partes:
I
I
Hipótese: Apresenta as informações conhecidas sobre o teorema.
Essas informações são tomadas como verdadeiras a fim de se
tentar obter uma demostração.
Tese: E a parte do teorema que desejamos validar, a partir da
hipótese, utilizando uma sequencia de argumentos formais.
Hipótese ⇒ Tese
>
Conceitos Básicos Quantificadores Exercı́cios
3/15
Lema e Corolário
• Em algumas circunstancias os teoremas recebem nomes
especiais.
I
I
Quando um teorema é utilizado como parte da demonstração
de um outro teorema, em geral mais complexo, ele recebe o
nome de Lema
Quando um teorema é uma consequência imediata de outro,
ele recebe o nome de Corolário. Por exemplo:
Teorema
A soma dos ângulos internos de um triangulo é 180 graus.
Corolário
Cada angulo de um triangulo equilátero vale 60 graus.
>
Conceitos Básicos Quantificadores Exercı́cios
4/15
Proposição
• Uma proposição pode ser falsa ou verdadeira. Caso seja
encontrada uma prova, ela se tornara um teorema. Exemplos:
Proposição
Para n ≥ 1, n 2 + n + 5 é um número primo.
Proposição
Tudo numero múltiplo de 6 e múltiplo de 3
Proposição
Existem infinitas de triplas de naturais (x , y, z ) tais que x 2 + y 2 = z 2
>
Conceitos Básicos Quantificadores Exercı́cios
5/15
Proposição
• Uma proposição pode ser falsa ou verdadeira. Caso seja
encontrada uma prova, ela se tornara um teorema. Exemplos:
Proposição
A série
Pn
i=1 1/i
diverge
Proposição
Existem infinitos números primos
Proposição
O algoritmo Heapsort realiza no máximo 5n log n comparações para
ordenar uma lista de n números
>
Conceitos Básicos Quantificadores Exercı́cios
6/15
Definições
• Definição é a enumeração das propriedades que um determinado
objeto (matemático ou não) deve obrigatoriamente ter (ou deixar
de ter) para pertencer a uma determinada classe de objetos.
Definição
Um inteiro p é primo se e somente se for divisı́vel por exatamente
quatro números: 1, −1, p e −p.
Definição
O módulo |r | de um número real r é r , se r ≥ 0, ou −r , se r < 0.
>
Conceitos Básicos Quantificadores Exercı́cios
7/15
Definições
• Evidententemente, toda definição é correta. Não há necessidade
(ou maneira) de prová-la.
• Há casos, contudo, em que uma mesma entidade recebe duas
diferentes definições. Quando isso ocorre, é necessário provar que
as definições se equivalem.
>
Conceitos Básicos Quantificadores Exercı́cios
8/15
Axioma
• Um axioma é uma afirmação básica aceita por todos acerca de
um algo. Axiomas são normalmente informações óbvias,
baseadas no senso comum:
Axioma
Todo número inteiro tem um único sucessor.
Axioma
Entre dois pontos distintos no plano existe uma única reta.
>
Conceitos Básicos Quantificadores Exercı́cios
9/15
Quantificadores
• O quantificador todo é representado por ∀, e muitas vezes
utilizamos o termo qualquer que seja em seu lugar
• O quantificador existe é denotado por ∃
• Frequentemente, torna-se necessário encontrar a negação de
uma asserção. Nesse momento é fundamental compreender
perfeitamente o significado dos quantificadores.
>
Conceitos Básicos Quantificadores Exercı́cios
10/15
Quantificadores
• Frequentemente, torna-se necessário encontrar a negação de
uma asserção. Nesse momento é fundamental compreender
perfeitamente o significado dos quantificadores:
Proposição
Todo número cuja soma dos dı́gitos (na base 10) é um múltiplo 3 é
divisı́vel por 3.
Proposição
Existe um número que não é divisı́vel por 3 cuja soma dos dı́gitos
(na base 10) é um múltiplo de 3.
>
Conceitos Básicos Quantificadores Exercı́cios
11/15
Quantificadores
• Frequentemente, torna-se necessário encontrar a negação de
uma asserção. Nesse momento é fundamental compreender
perfeitamente o significado dos quantificadores:
Proposição
Toda tripla de números inteiros x , y e z é tal que x 2 + y 2 6= z 2 .
Proposição
Existe uma tripla de números inteiros x , y e z tal que x 2 + y 2 = z 2 .
>
Conceitos Básicos Quantificadores Exercı́cios
12/15
Exercı́cios
• Exercı́cio 1 - Seja I um intervalo, e f : I → R uma função
contı́nua. Reescreva as seguintes propostas utilizando
quantificadores:
a - A função f é constante
b - A função f não é constante
c - A função f atinge o valor zero
>
Conceitos Básicos Quantificadores Exercı́cios
13/15
Exercı́cios
• Exercı́cio 2 - Seja f : R → R uma função. Negue as
seguintes propostas:
a - ∀x ∈ R, f (x ) 6= 0.
b - ∀M > 0, ∃A > 0, ∀x ≥ A, f (x ) > M .
c - ∀x ∈ R, f (x ) > 0 ⇒ x ≤ 0.
>
Conceitos Básicos Quantificadores Exercı́cios
14/15
Exercı́cios
• Exercı́cio 3 - Determine se cada proposta é verdadeira ou
falsa
a - ∃x ∈ R∗ , ∀y ∈ R∗ , ∀z ∈ R∗ , z − xy = 0
b - ∀y ∈ R∗ , ∃x ∈ R∗ , ∀z ∈ R∗ , z − xy = 0
c - ∀y ∈ R∗ , ∀z ∈ R∗ , ∃x ∈ R∗ , z − xy = 0
d - ∃a ∈ R∗ , ∀ > 0, |a| < e - ∀ > 0, ∃a ∈ R∗ , |a| < >
Conceitos Básicos Quantificadores Exercı́cios
15/15