Aula 16

Prévia do material em texto

CCT0350 – MATEMÁTICA APLICADA A COMPUTAÇÃO 
Aula 16: Métodos de Demonstração 
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 
 
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)) 
 
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. 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
Métodos de Demonstração 
AULA 16: Métodos de Demonstração 
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. 
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 ? 
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 
 
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 
 
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 
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,...}. 
 
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 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
Métodos de Demonstração 
AULA 16: Métodos de Demonstração 
Exemplo: Para todo n ∊ N, 
 
 
 
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. 
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) 
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. 
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, 
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. 
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 é, 
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. 
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 
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 
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ívelpor 3. 
 
 
Exercícios Propostos 
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. 
 
 
 
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: 
 
 
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. 
 
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 
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 
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. 
 
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 
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