Exercicios Matemática Discreta

131 x Px 132 x Px 133 x Px 134 x Px 135 x x 3 Px x Px 14 Considere o predicado Px x 1 2x Quais são os valores lógicos das proposições abaixo indicadas sabendo que o universo U é o conjunto dos números inteiros Z 141 Q0 142 Q1 143 Q1 144 x Qx 145 x Qx 146 x Qx 147 x Qx 15 Seja o predicado Qx yz x y z Quais os valores lógicos das proposições x y z Qxyz e z x y Qxyz sabendo que o universo U é o conjunto dos números reais R 16 Traduza a proposição x Cx y Cy Fxy para português onde Cx x tem um computador Fxy x e y são amigos e o universo U é o conjunto de todos os alunos da UniCV 17 Diga justificando se as proposições abaixo indicadas são verdadeiras ou falsas sabendo que o universo U é igual ao conjunto ℝ 171 x y xy y 172 x y z x y z 173 x y x 0 y 0 x y 0 18 Mostre que a Resolução é uma regra de inferência 19 Para cada grupo de premissas abaixo indicadas Que conclusões relevantes podem ser tiradas Explique as regras de inferências utilizadas para obter cada uma dessas conclusões 191 Se eu jogo hóquei então eu fico dolorido Eu uso hidromassagem se eu estou dolorido Eu não usei hidromassagem 192 Todo estudante tem conta na Internet Homer não tem conta na internet Maggie tem conta na internet 20 Determine se cada um dos argumentos seguintes é válido ou inválido e explique porque 201 Todo graduando em Ciência de Computação CC faz Matemática Discreta MD Natasha está fazendo MD Por isso Natasha é uma graduanda em CC 202 Todos os papagaios gostam de frutas Meu passarinho de estimação não é um papagaio Por isso meu passarinho de estimação não gosta de frutas 6 Escreva as proposições abaixo indicadas na forma se p então q em português 61 É necessário lavar o carro do chefe para ser promovido 62 Ventos do sul implicam um degelo primaveril 63 Uma condição suficiente para a garantia ser válida é que tenha comprado o computador em menos de um ano 64 Leo é pego sempre que ele trapaceia 65 Podese acessar ao site só se se pagar uma taxa de assinatura 7 Numa ilha há dois tipos de habitantes cavaleiros que sempre falam verdade e bandidos que sempre mentem Suponhamos que encontres duas pessoas A e B Quem são A e B se A diz B é um cavaleiro e B diz Nós dois somos tipos opostos de habitantes 8 Verifique se as proposições p q r e p q r são logicamente equivalentes ou não 9 Mostre que x Px Qx e x Px Qx são logicamente equivalentes 10 Considere os predicados Px a palavra x contém a letra a e Qx y x é capital de y Quais são os valores de verdade das proposições abaixo indicadas 101 Porange 102 QPorto Portugal 103 Plemon 104 Ptrue 105 Pfalse 106 QPraia Cabo verde 11 Transcreva as proposições abaixo indicadas para português considerando que os predicados Cx x é um comediante e Fx x é divertido e o universo como o conjunto de todas as pessoas 111 x Cx Fx 112 x Cx Fx 113 x Cx Fx 114 x Cx Fx 12 Assumindo que o universo consiste em todos os pássaros mostre que a partir das premissas Todos os beijaflores são ricamente coloridos Nenhum pássaro grande vive de néctar e Pássaros que não vivem de néctar são monótonos nas cores podese concluir Beijaflores são pequenos 13 Suponha que o domínio do predicado Px seja o conjunto U 12345 Expresse as proposições abaixo indicadas sem usar quantificadores mas apenas conjunções disjunções e negações 1 Utilizando as equivalências lógicas já conhecidas mostre que 11 p q p r p q r 12 p r q r p q r 13 p q p q 14 p q p q 15 p p q p 2 Utilizando tabela de verdade mostre que 21 p q p r p q r 22 p r q r p q r 23 p q p q p q 24 p p q p 3 Considere que p e q são as proposições É permitido nadar na praia e Foram descobertos tubarões perto da praia respectivamente Expresse cada uma das proposições compostas abaixo indicadas como uma sentença em português 31 q 32 p q 33 p q 34 p q 35 q p 36 q p 37 p q 38 p p q 4 Considere que p e q são as proposições A temperatura está abaixo de zero e Está nevando respectivamente Escreva as proposições abaixo indicadas usando p q e conectivos lógicos 41 A temperatura está abaixo de zero e está nevando 42 A temperatura está abaixo de zero mas não está nevando 43 A temperatura não está abaixo de zero e não está nevando 44 Ou a temperatura está abaixo de zero ou está nevando ou os dois 45 Para que a temperatura esteja abaixo de zero é necessário e suficiente que esteja nevando 5 Diga se as seguintes proposições são verdadeiras ou falsas 51 0 1 se e somente se 1 2 52 Se 1 1 2 então 2 2 5 53 1 1 3 se e somente se os macacos puderem voar 54 Cachoros podem voar se 2 2 5 55 A condição suficiente e necessário para que 1 1 2 é que o pato nade 56 1 1 3 somente se porco fala português Questoes Prof Matheus 1 11 p q p r p q r Para mostrar essa equivalˆencia vamos trabalhar nos dois lados da expressao Lado esquerdo p q p r p q p r p q r p Associatividade p p q r Comutatividade p q r Idempotˆencia Lado direito p qr Vamos reescrever a implicacao usando a equivalˆencia p q p q p q r p q r Vamos provar que p q r e equivalente a p q r 1 p q r p q r Se p q r e verdadeiro entao p e verdadeiro e q r e verdadeiro Entao q r e verdadeiro Assim p q r e verdadeiro porque q r e verdadeiro 2 p q r p q r Se p q r e verdadeiro temos duas possibilidades Se p e verdadeiro entao p e falso entao p q r e falso Se q r e verdadeiro entao pelo menos um de q ou r e verdadeiro Se p for verdadeiro entao p q r e verdadeiro se tanto q quanto r forem verdadeiros Mas isso nao contraria a equivalˆencia pois estamos verificando a veracidade da expressao original Portanto p q r p q r Logo p q p r p q r 12 p r q r p q r Lado esquerdo p r q r p r q r r p q Distributividade do sobre 1 Lado direito p q r Reescrevendo a implicacao p q r p q r p q r De Morgan Vamos mostrar que r p q p q r 1 r p q p q r Se r p q e verdadeiro r e verdadeiro e p q e verdadeiro Logo r e verdadeiro portanto p q r e verdadeiro pois r e verdadeiro 2 p q r r p q Se p q r e verdadeiro temos duas possibilidades Se pq e verdadeiro entao tanto p quanto q sao falsos Isso nao necessariamente torna r p q verdadeiro mas r pode ainda ser verdadeiro por si so Se r e verdadeiro entao r p q e verdadeiro se p q e verdadeiro que pode ser satisfeito se qualquer um de p ou q for verdadeiro Logo p r q r p q r 13 p q q p Isso e uma aplicacao direta da comutatividade da conjuncao p q q p 14 p q q p Isso e uma aplicacao direta da comutatividade da disjuncao p q q p 15 p p q p Lado esquerdo p Lado direito p q p Vamos expandir e simplificar o lado direito p q p p p q p Distributividade p q p Idempotˆencia p Absorcao pois p q p p Logo p p q p e uma tautologia Portanto cada uma das equivalˆencias fornecidas esta demonstrada utilizando as equivalˆencias logicas 2 2 Utilizando tabela de verdade 21 p q p r p q r p q r p q p r p q p r p q r T T T T T T T T T F T F T T T F T F T T T T F F F F F F F T T F F F F F T F F F F F F F T F F F F F F F F F F F As colunas pqpr e pqr sao idˆenticas portanto pqpr p q r e uma equivalˆencia valida 22 p r q r p q r p q r p r q r p r q r p q r T T T T T T T T T F F F F F T F T T F T T T F F F F F T F T T F T T T F T F F F F T F F T F F F T F F F F F F T As colunas p r q r e p q r sao idˆenticas portanto p r q r p q r e uma equivalˆencia valida 23 p q p q p q p q p q p q p q p q T T T T T T F T F T F T T F T F F F F F As colunas p q e p q p q nao sao idˆenticas portanto p q p q p q nao e uma equivalˆencia valida 24 p p q p p q p q p q p T T T T T F T T F T T F F F F F 3 As colunas p e p q p sao idˆenticas portanto p p q p e uma equivalˆencia valida 3 Considere que p e q sao as proposicoes E permitido nadar na praia e Foram descobertos tubaroes perto da praia respectivamente 1 Nao foram descobertos tubaroes perto da praia q 2 E permitido nadar na praia e foram descobertos tubaroes perto da praia p q 3 E permitido nadar na praia ou foram descobertos tubaroes perto da praia p q 4 Se e permitido nadar na praia entao foram descobertos tubaroes perto da praia p q 5 Se foram descobertos tubaroes perto da praia entao e permitido nadar na praia q p 6 Nao e permitido nadar na praia p 7 E permitido nadar na praia se e somente se foram descobertos tubaroes perto da praia p q 8 Nao e permitido nadar na praia ou e permitido nadar na praia e nao foram descobertos tubaroes perto da praia p p q 4 Considere que p e q sao as proposicoes A temperatura esta abaixo de zero e Esta nevando respectivamente 1 A temperatura esta abaixo de zero e esta nevando p q 2 A temperatura esta abaixo de zero mas nao esta nevando p q 3 A temperatura nao esta abaixo de zero e nao esta nevando p q 4 Ou a temperatura esta abaixo de zero ou esta nevando ou os dois p q 5 Para que a temperatura esteja abaixo de zero e necessario e suficiente que esteja nevando p q 4 5 1 0 1 se e somente se 1 2 Esta proposicao e falsa pois 0 1 e falso e 1 2 tambem e falso 2 Se 1 1 2 entao 2 2 5 Esta proposicao e falsa A primeira parte da proposicao e verdadeira 1 1 2 mas a segunda parte 2 2 5 e falsa 3 1 1 3 se e somente se os macacos puderem voar Esta proposicao e falsa A primeira parte 1 1 3 e falsa e a segunda parte os macacos podem voar e falsa 4 Cachorros podem voar se 2 2 5 Esta proposicao e verdadeira mas a sua conclusao e falsa 2 2 5 e falso e cachorros nao podem voar 5 A condicao suficiente e necessaria para que 1 1 2 e que o pato nade Esta proposicao e falsa Embora o pato possa nadar isso nao e uma condicao suficiente e necessaria para 1 1 2 6 1 1 3 somente se porcos falam portuguˆes Esta proposicao e falsa A primeira parte 11 3 e falsa mas a segunda parte porcos falarem portuguˆes nao esta relacionada a veracidade da proposicao inicial 6 1 E necessario lavar o carro do chefe para ser promovido Se for necessario lavar o carro do chefe entao sera promovido 2 Ventos do sul implicam um degelo primaveril Se houver ventos do sul entao havera um degelo primaveril 3 Uma condicao suficiente para a garantia ser valida e que tenha comprado o computador em menos de um ano Se comprou o computador em menos de um ano entao a garantia e valida 4 Leo e pego sempre que ele trapaceia Se Leo trapaceia entao ele e pego 5 Podese acessar ao site so se se pagar uma taxa de assinatura Se pagar uma taxa de assinatura entao podese acessar ao site 7 A diz B e um cavaleiro Se A e um cavaleiro entao B e um cavaleiro Se A e um bandido entao B e um cavaleiro B diz Nos dois somos tipos opostos de habitantes Se B e um cavaleiro entao A e um bandido Se B e um bandido entao A e um cavaleiro Portanto considerando que as duas declaracoes sao mutuamente exclusivas se A diz a verdade entao B e um cavaleiro e se A mente entao B e um bandido 5 8 Vamos verificar a equivalˆencia das proposicoes pq gr p q r pq gr T T T T T T F F T F T T T F F T F T T T F T F T F F T T F F F T A coluna pq gr e igual a coluna pq gr portanto as proposicoes sao logicamente equivalentes 9 Vamos mostrar a equivalˆencia das proposicoes Px Qx e Px Qx Se Px e verdadeira e Qx e verdadeira entao Px e verdadeira e Qx e falsa e uma contradicao Portanto as proposicoes sao logicamente equivalentes 10 1 Porange Verdadeiro pois a palavra orange contem a letra a 2 QPorto Portugal Verdadeiro pois Porto e capital de Portugal 3 Plemon Falso pois a palavra lemon nao contem a letra a 4 Ptrue Verdadeiro pois a palavra true contem a letra a 5 Pfalse Falso pois a palavra false nao contem a letra a 6 QPraia Cabo Verde Falso pois Praia nao e capital de Cabo Verde 11 Considerando Cx como x e um comediante e Fx como x e divertido 1 Todo comediante e divertido 2 Todo comediante e divertido 3 Se alguem e comediante entao e divertido 4 Alguem e comediante e e divertido 6 12 Assumindo Bx como x e um beijaflor Rx como x e ricamente colorido e Nx como x vive de nectar Premissas 1 Todos os beijaflores sao ricamente coloridos xBx Rx 2 Nenhum passaro grande vive de nectar xPassaroGrandex Nx 3 Passaros que nao vivem de nectar sao monotonos nas cores xNx MonotonoNasCoresx Conclusao Beijaflores sao pequenos xBx Pequenox 13 Supondo Px como x e verdadeiro 1 3Px P3 e verdadeiro 2 V xPx Todos os elementos em U sao verdadeiros 3 3Px P3 e verdadeiro 4 V Px Nao e verdade que todos os elementos em U sao verdadeiros 5 V x 3 Px 3Px Se x 3 e um elemento em U entao Px e P3 sao verdadeiros 14 Considerando o predicado Px x12x 1 Q0 Verdadeiro pois 0 1 2 0 2 Q1 Falso pois 1 1 2 1 3 Q1 Verdadeiro pois 1 1 2 1 4 Qx Verdadeiro pois existe pelo menos um numero inteiro para o qual x 1 2x por exemplo x 0 ou x 1 5 xQx Verdadeiro pois para todos os numeros inteiros x 1 2x e verdadeiro por exemplo x 0 1 1 2 2 6 Qx Falso pois sempre existe pelo menos um numero inteiro para o qual x 1 2x 7 Qx Verdadeiro pois sempre existe pelo menos um numero inteiro para o qual x 1 2x 7 15 Considerando o predicado Qx y z x y z 1 Qx y z Depende dos valores de x y e z Pode ser verdadeiro ou falso dependendo da escolha de x y e z 2 xyzQx y z Falso pois nem todos os numeros reais x y e z sat isfazem a equacao x y z Por exemplo se x 1 y 1 e z 3 a equacao nao e satisfeita 16 Considerando Cx x tem um computador e Fx y x e y sao amigos onde o universo U e o conjunto de todos os alunos da UniCV xCx yCy Fx y Todo aluno tem um computador ou existe um amigo do aluno que tem um computador 17 Considerando o universo U como o conjunto dos numeros reais R 1 xy y Falso pois nem todos os numeros reais x e y sao iguais 2 x y z Verdadeiro pois para cada par de numeros reais y e z existe um numero real x tal que x y z 3 x 0 y 0 x y 0 Verdadeiro pois para todos os numeros reais x e y maiores ou iguais a zero a diferenca entre x e y e maior que zero 18 A resolucao e uma regra de inferˆencia baseada no princıpio da refutacao por contradicao Ela e usada em logica proposicional para deduzir novas proposicoes a partir de outras 19 191 Premissas 1 Se eu jogo hoquei entao eu fico dolorido 2 Eu uso hidromassagem se eu estou dolorido 3 Eu nao usei hidromassagem Conclusao 8 Podemos concluir que Eu nao jogo hoquei A regra de inferˆencia utilizada e a modus tollens que afirma que se temos uma implicacao p q e sabemos que q e falso entao podemos inferir que p tambem e falso 192 Premissas 1 Todo estudante tem conta na Internet 2 Homer nao tem conta na Internet 3 Maggie tem conta na Internet Conclusao Podemos concluir que Maggie nao e um estudante A regra de inferˆencia utilizada e a negacao do universal que afirma que se todo X tem uma propriedade P e sabemos que um X especıfico nao tem essa propriedade entao podemos concluir que esse X especıfico nao pertence ao conjunto definido pelo universal 20 201 Premissas 1 Todo graduando em Ciˆencia de Computacao CC faz Matematica Discreta MD 2 Natasha esta fazendo MD Conclusao Natasha e uma graduanda em CC Validade Valido Esse argumento segue a regra de inferˆencia do silogismo hipotetico que afirma que se temos uma implicacao p q e tambem q entao podemos inferir p 202 Premissas 1 Todos os papagaios gostam de frutas 2 Meu passarinho de estimacao nao e um papagaio Conclusao Meu passarinho de estimacao nao gosta de frutas 9 Validade Invalido Esse argumento nao segue uma regra de inferˆencia valida A premissa Todos os papagaios gostam de frutas nao esta dire tamente relacionada a conclusao sobre o passarinho de estimacao 10