apresentacao da aula 16

Prévia do material em texto

CCT0350 – MATEMÁTICA APLICADA A COMPUTAÇÃO
Aula 16: Métodos de Demonstração
1
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
 Técnicas Adicionais, envolvendo quantificadores.
Equivalência em Quantificadores
Definição. Sentenças envolvendo quantificadores e predicados são logicamente equivalentes se, e somente se, elas têm a mesma tabela verdade, não importa quais predicados são substituídos nessas sentenças e que domínio é usado para variáveis nestas funções proposicionais.
Notação: S  T
2
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
 Técnicas Adicionais, envolvendo quantificadores.
Quantificadores Aninhados
Dois quantificadores estão aninhados se um está no escopo do outro, onde o quantificador mais interno é tratado como uma função proposicional. 
Exemplo: ∀x y (x+y=0) é o mesmo que ∀xQ(x) em que Q(x) é  yP(x,y) e P(x,y) 
é x+ y = 0
Exemplo: ∀x y ((x> 0)^(y<0)  (xy < 0))
3
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
 Técnicas Adicionais, envolvendo quantificadores.
Quantificadores Aninhados
Exemplo: Seja Q(x,y) a sentença x + y = 0. Quais os valores verdade das quantificações  y∀x Q(x,y) e ∀x  y Q(x,y) com x pertencente a R e y pertencente a R.
A quantificação onde Q(x,y) é x+ y = 0 representa a afirmação existe um  y∀x Q(x,y) 
número real y para todo número real x para o qual x + y = 0. Como não exista nenhum
número real y que somado a todo real x resulta em zero, então a sentença  y∀x Q(x,y) é falsa.
 ∀x  y Q(x,y) onde x + y = 0 é verdade pois para cada x, existe um y = -x cuja soma x + y
resulta em 0.
4
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
5
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Exemplo: Seja S(x, y, z) a declaração x + y = z. Quais são os valores verdade das
Declarações e , com x, y, z pertencente a R ?
Linguagem natural 
 :: todo real x e y, existe um real z para o qual x +y = z, que é verdadeira visto que a soma de dois números reais resulta em um número real.
 
 : existe Já a quantificação é interpretada em linguagem natural como existe
um número real z tal que para todo real x e y, x + y = z. Como inexiste tal número, então
a quantificação correspondente é falsa.
6
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Construção dos Números Naturais como Função: Princípio da Indução
https://ccbela.wordpress.com
Será tal afirmação verdadeira sempre? 
Vale para qualquer
número natural ?
7
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Construção dos Números Naturais como Função: Princípio da Indução
Exemplo: 1+2+...+n= [n(n+1)]/2 , para todo número natural n 1
Observe: 
(1) Sn= 1+ 2+ 3+ …+ (n-2)+(n-1)+n
ou mesmo:
(2) Sn= n+ (n-1) +(n-2) +…+ 3+2+1
8
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Construção dos Números Naturais como Função: Princípio da Indução
Exemplo: 1+2+...+n= [n(n+1)]/2 , para todo número natural n 1
Observe: 
(1) Sn= 1+ 2+ 3+ …+ (n-2)+(n-1)+n
ou mesmo:
(2) Sn= n+ (n-1) +(n-2) +…+ 3+2+1
2 Sn = (n+1)+(n+1) +(n+1) + ...+ (n+1) = n(n+1)  Sn = [n (n+1)]/2
9
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Construção dos Números Naturais como Função: Princípio da Indução
Exemplo: 1+2+...+n= [n(n+1)]/2 , para todo número natural n 1
Observe: 
(1) Sn= 1+ 2+ 3+ …+ (n-2)+(n-1)+n
ou mesmo:
(2) Sn= n+ (n-1) +(n-2) +…+ 3+2+1
2 Sn = (n+1)+(n+1) +(n+1) + ...+ (n+1) = n(n+1)  Sn = [n (n+1)]/2
Observação: Progressão aritmética qualquer de n termos, cujo primeiro termo é a1 e cujo enésimo termo é an, para obtermos Sn = [n (a1 + an)]/2
10
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
A Sequência dos números Naturais 
números Naturais = modelo matemático = uma escala padrão
 
 
	 Permite a operação de contagem.
Conjunto dos Números Naturais
Notação: N 
N= {1, 2, 3, 4, 5,...}.
11
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Princípio da Indução
Seja p(.) uma função proposicional em N. Se p(1) é verdade e para todo m em N, p(m)
implica p(m+1), então, p(n) é verdade para todo n em N, isto é,
Seja S um subconjunto de N que satisfaz:
(i) 1 ∊ S.
(ii) ∀ n ∊ S )  (n + 1) ∊ S.
Então, S = N
12
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Exemplo: Para todo n ∊ N,
13
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Exemplo: Para todo n ∊ N,
Para n = 1. 
14
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Exemplo: Para todo n ∊ N,
Para n = 1. 
Agora vamos assumir que é valido para m ∊ N (hipótese de indução)
15
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Exemplo: Para todo n ∊ N,
Para n = 1. 
Agora vamos assumir que é valido para m ∊ N (hipótese de indução)
Para m+1:
Logo, o resultado é valido para todo n ∊ N.
16
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Exemplo: Fixado x > 0, para todo n ∊ N,
17
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Exemplo: Fixado x > 0, para todo n ∊ N,
De fato:
Logo, a proposição é válida para n = 1. 
18
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Exemplo: Fixado x > 0, para todo n ∊ N,
De fato:
Logo, a proposição é válida para n = 1. 
Vamos assumir que o resultado é válido para m ∊ N (hipótese de indução), isto é,
19
MATEMÁTICA APLICADA A COMPUTAÇÃO
Métodos de Demonstração
AULA 16: Métodos de Demonstração
Exemplo: Fixado x > 0, para todo n ∊ N,
De fato:
Logo, a proposição é válida para n = 1. 
Vamos assumir que o resultado é válido para m ∊ N (hipótese de indução), isto é,
Para m+1:
Logo, o resultado é válido para todo n ∊ N.
20
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de Demonstração
Sugestão de resolução dos exercícios propostos.
1- Traduza a declaração A soma de dois inteiros positivos é sempre positivo em uma expressão lógica.
Exercícios Propostos
21
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de Demonstração
Sugestão de resolução dos exercícios propostos.
1- Traduza a declaração A soma de dois inteiros positivos é sempre positivo em uma expressão lógica.
Solução: Podemos escrever: Para cada dois números inteiros, se ambos são positivos, então, o resultado da soma desses dois inteiros é positivo.
2º Passo do refinamento: consiste em incluir variáveis. 
	Para todos os inteiros positivos x e y, x + y é positivo.
3º Passo: Última sentença em uma expressão lógica é quase direta, e resulta em: 
Se mudarmos o domínio da quantificação, a expressão acima pode ser representada de outra maneira ainda:
A declaração 
A soma de dois inteiros positivos é sempre positivo foi traduzida em termos formais como 
Exercícios Propostos
22
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de Demonstração
Sugestão de resolução dos exercícios propostos.
2- Para todo n ∊ N,n3 - n é divisível por 3.
Exercícios Propostos
23
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de Demonstração
Exercícios Propostos
Sugestão de resolução dos exercícios propostos.
2- Para todo n ∊ N,n3 - n é divisível por 3.
Solução:
1o. Passo: Se n = 1 então, 13 - 1 = 1 - 1 = 0 = 3 x 0 .Logo a proposição é valida para n = 1. 
24
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de DemonstraçãoExercícios Propostos
Sugestão de resolução dos exercícios propostos.
2- Para todo n ∊ N,n3 - n é divisível por 3.
Solução:
1o. Passo: Se n = 1 então, 13 - 1 = 1 - 1 = 0 = 3 x 0 .Logo a proposição é valida para n = 1. 
2º Passo: Vamos assumir que o resultado é valido para m ∊ N (hipótese de indução):
Temos então: 
25
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de Demonstração
Exercícios Propostos
Sugestão de resolução dos exercícios propostos.
2 - Para todo n ∊ N,n3 - n é divisível por 3.
Solução:
1o. Passo: Se n = 1 então, 13 - 1 = 1 - 1 = 0 = 3 x 0 .Logo a proposição é valida para n = 1. 
2º Passo: Vamos assumir que o resultado é valido para m ∊ N (hipótese de indução):
Temos então: 
3º Passo: 
Logo é valido para todo n pertencente a N.
26
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de Demonstração
Exercícios Propostos
Sugestão de resolução dos exercícios propostos.
3- Prove por indução matemática que
27
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de Demonstração
Sugestão de resolução dos exercícios propostos.
Exercícios Propostos
28
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de Demonstração
Exercícios Propostos
Sugestão de resolução dos exercícios propostos.
29
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de Demonstração
Indicação de Leitura Específica
 Recomendamos a leitura do capítulo referente Teoria de Conjuntos no material didático.
 Acesse a Biblioteca Virtual da Estácio e pesquise mais exercícios nos livros de Teoria de Conjuntos disponíveis.
Sugestão de leitura:
http://www.somatematica.com.br/emedio/funcao1/funcao1.php
Indicação de Leitura
30
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 16: Métodos de Demonstração
Indicação de Leitura Específica
Sugestão de leitura:
https://docente.ifrn.edu.br/cleonelima/disciplinas/fundamentos-de-programacao-2.8401.1m/fundamentos-de-logica-e-algoritmos-1.8401.1v/apostila-equivalencias-logicas
Indicação de Leitura
31
32