Resumo Matematica Discreta P1 - PUC RIO

Prévia do material em texto

28/02/2012
Aula 1
Christine
www.mat.puc-rio.br
Disciplinas online - graduação - mat discreta
	 	 	 	 	 	 
	 	 	 	 	 	 Conceitos de lógica matemática
 
Double-Tap to Edit
Proposicao - qualquer afirmação para a qual pode-se atribuir um valor falso [F] ou 
verdadeiro [V]. Geralmente e notada por uma letra minúscula
Exemplo-
	 	 a. p= hoje terca-feira
	 	 	 	 VL[p] = V
	 	 b. q= 2 2 = 5
	 	 	 	 VL[q] = F
	 	 valor lógico 
Operadores lógicos - tarnsformam proposicoes simples em proposicoes compostos. 
sao eles=
Operador	 	 Simbolo	 Proposicao composta	le-se
Disjuncao	 	 v	 	 	 p v q	 	 	 	 	p ou q
Conjuncao	 	 	 	 	 p q	 	 	 	 	p e q
Condicional		 	 	 	 p q	 	 	 	 	se p entao q
	 	 	 	 	 	 	 	 	 	 	 	 	p e condição suficiente para q
	 	 	 	 	 	 	 	 	 	 	 	 	q e condição suficiente para p
Bicondicional	 	 	 	 p q	 	 	 	 	p se e somente se q
Alem dos operadoes, tem-se o modificador negação que troca o valor lógico da 
proposição - símbolos 
p p
V	 	 F
F	 	 V
P1
Diz-se que duas proposições compostas com as mesmas proposicoes simples sao 
equivalentes quando suas tabelas verdade sao idênticas [ultima coluna]
Algumas equivalencias-
01/03/2012
Aula 2
Ex 1. Sabendo que VL[p] = F e VL[q] = V, determine o valor lógico de:
Ex 2. Moster que a proposição é uma TAUTOLOGIA 
(proposição verdadeira independentemente do VL das proposições simples que 
possui)
Ex 3. Dados U=[-2, -1, 0, 1, 2]
	 p(x) : x>=0
	 q(x) : x é par
	 	 I) Apresente o conjunto verdade dos predicados:
	 	 	 a) p(x) -> ~q(x)
	 	 	 b) ~(p(x) v q(x))
*resolvendo por equivalencias em vez de 
tabela verdade
** -2 e -1, porque faz com que o antecedente 
seja falso, assim a solução já é verdadeira.
1, porque se o antecedente é verdadeiro, o 
consequente também tem que ser verdadeiro
então queremos valores que não 
estão nos conjuntos verdades p e q
	 II) Dê o VL
	 	 a)
	 	 b)
4. Ex 4.
Ex 5. U = conjunto de pessoas casadas sem bigamia
C(x,y) = x é casado com y
Ex 6. OBS Negação com Quantificação
Ex: dê a negação 
Ex. A soma de dois números primos é um neumero primo. F ou V?
Falso - basta apresentar um contra-exemplo. 3+5=8
[x é primo ^ y é primo -> x + y é primo?]
Algumas técnicas de Demonstração
1. Prova Direta Mostar a veracidade de uma 
afirmação na forma de uma 
condicional assumindo o antecedente 
(hipótese) verdadeiro e chegando na 
veracidade do consequente (tese)
A soma de 2 números impares e um numero par
2. Prova indireta - aplicar a prova direta na contrapositiva
3. Contradição ou ABSURDO
06/03/2012
Aula 3
Continuação de Absurdo
Ex. b. O conjunto dos números primos é infinito
Suponha que o conjunto P dos números primos é finito.
Seja p o maior numero primo
Então P = {2, 3, 5, 7, ... , p} é o conjunto dos primos
Seja r= 2, 3, 5, ... , p (r é o produto dos primos r>p)
Seja um primo qualquer...
é verdade que logo r + 1 não é divisível por 
nenhum primo.
Então r + 1 é primo maior que p.
Como p era o maior primo... 
(contradição)
4. Indução Finita
2x3x5x...xp
4. Indução Finita
É geralmente utilizada para demonstrar que uma propriedade P(n) é válida 
para todo n>=m
Consiste de 2 etapas:
	 (i) Mostrar que P(m) é verdadeira 
	 (ii) Provar a condicional P(k) -> P(k+1) , k>= m
Ex.
d.1. determine o menor natural m que satisfaz P(n)
d.2. prove por indução
Seja t o n-ésimo numero tirangular.
t indica o numero de pontos na configuração geométrica do numero triangular.
assim 
a Expresse t em função de t
b Procure uma fórmula fechada para a
c Mostre por indução a fórmula encontrada em bDouble-Tap to Editfórmula encontrada em b
Problemas Recursivos
08/03/2012
Aula 4
Problemas Recursivos
1. Números triangulares
2. Seja x o numero máximo de regiões que n retas dividem um plano
	 a. Expresse x recursivamente
b. encontre uma fórmula fechada para x
c. prove por induçãao
3. O problema da torre de Hanói
Dados - 3 hastes, n discos de diâmetros todos distintos dispostos em 
uma das hastes em ordem decrescente de seus tamanhos
x - o número mínimo de movimentos necessários para resolver o 
problema
	 a. expresse x recursivamente
Comparando x3 com x2, ate o 3o 
movimento o x3 é igual ao x2, e ate 
esse movimento a peça maior fica 
parada. depois é so mexer a grande de 
lugar e repetir o procedimento 
voltando - que é igual a de ida
b. escreva a formula fechada
c. prove por indução
4. Observe a seqüência de Fibonacci [0, 1, 1, 2, 3, 5, 8, ...]
	 a. Expresse recursivamente
b. Sabendo que Demonstre por indução
13/03/2012
Aula 5
Problemas de contagem
Permutação de n elementos distintos
Ex: 1) determine o numero de anagramas 
da palavra FRASE
Ex: 2) Quantos dos anagramas d palavra FRASE tem as vogais todas juntas?
Permutação com repetição
Ex: 1) Quantos sao os anagramas da palavra ARARAS?
2) quantas anagramas da palavra ARARAS tem as consoantes juntas?
Numeros binomiais
Algumas interpretações
	 	 Significa o numero de maneiras distintas de se escolher p elementos 
de um conjunto de n elementos
Ex. Quantas comissões de 4 pessoas pode-se formar escolhidas de um grupo de 
6 pessoas?
	 	 Indica o numero de subconjuntos de p elementos de um conjunto 
com n elementos
Ex. Sabendo que , determine o numero de subconjuntos de que 
contem exatamente 2 elementos
e quantos subconjuntos A tem ao todo
	 	 significa o coeficiente de no desenvolvimento 
Resolva os problemas
1. Estando em um ponto (x,y) do plano cartesiano, uma particula desloca-se ou para 
o ponto (x+1, y) ou para o ponto (x, y+1). Quantos trajetos distintos esta particula 
pode fazer da origem ao ponto (6,4)?
Independente do 
caminho vou 4 pra 
cima e 6 pra 
direita, qualquer 
caminho que faço é 
uma permutação 
dos possíveis 
caminhos que 
posso fazer
2. Quantos trajetos da questão 1 passam pelo ponto (2,2)?
3. Quantas são as soluções inteiras positivas da equação x+y+z= 7 ?
4. Quantas são as soluções inteiras não negativas da questão 3?
5. Resolva o problema 3 de outar maneira
15/03/2012
Aula 6
continuação...
6. Determine o numero de soluções inteiras positivas da equação x+y+z=21 sendo x, y 
e z ímpares
7. Determine o numero de soluções inteiras positivas da equação x y z t = 2048
8. Determine o numero de soluções inteiras positivas da inequação x+y+z<8
Double-Tap to EditTriângulo de Pascal
Propriedades
1. Relação de Stifel
A soma de 2 elementos consecutivos quaisquer na linha, 
será o valor de uma linha abaixo, na próxima coluna
2. Complementaridade
	 Relação simétrica nas linhas, o primeiro elemento igual ao 	
	 ultimo, até chegar no meio
3. Teorema das linhas [desenho]
4. Teorema das colunas [desenho]
5. Teorema das diagonais [desenho]
Ex.
a. Calcule a soma
20/03/2012
Aula 7
Binômio de Newton
OBS-
1. No desenvolvimento de tem-se exatamente n 1 termos.
2. Os coeficientes no desenvolvimento de são os elementos da linha n do 
triângulo de Pascal.
3. Organizando o desenvolvimento de pelas potências decrescentes de X, 
tem-se que um termo genérico pode ser expresso como 
Ex 1. Determine o coeficiente de em
Ex 2. Determine o coeficiente de em 
Ex 3. Qual a soma dos coeficientes do desenvolvimento de 
Ex 4. Qual é o termo máximo do desenvolvimento de 
	 	 	 	 	 Princípio das Gavetas ou da Casa de Pombos
Se n objetos são colocados em no máximo n - 1 gavetas então pelo menos uma gaveta 
tem pelo menos 2objetos.
Ex 1. Qual o número mínimo de pessoas necessárias para que se possa 
garantir que quatro delas nasceram no mesmo mês?
Ex 2. Mostre que em qualquer conjunto de 7 inteiros, existe um par cuja soma 
ou cuja diferença é divisível por 10.
na diferença - os números que tiverem o mesmo final - o mesmo resto quando 
dividido por 10 - será divisível por 10 quando subtraídos.
na soma - os números que tiverem a soma dos números finais igual a 10 - 
quando o resto de um dos números quando dividido por 10 mais o resto do 
outro quando dividido por 10 somam a 10.
na gaveta 1 coloque todos os números que tem o resto 0 na divisão por 10
2
3
4
5
6
1 ou 9
2 ou 8
3 ou 7
4 ou 8
5
assim pelo prinípio das gavetas ha pelo menos 1 gaveta com pelo menos 2 
inteiros.
Caso eles tenham o mesmo resto, a diferença é múltiplo de 10
Caso eles tenham o restos diferentes, a soma é múltiplo de 10
OBS- Nas gavetas 1 e 6 tanto a soma como a diferença são múltiplos de 10