Baixe o app para aproveitar ainda mais
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
Compartilhar