Lista de Exercícios Resolvida - Fundamentos da Lógica Proposicional UFMG

Lista de Exercícios 1 Soluções Fundamentos da Lógica Lógica Proposicional UFMGICExDCC DCC111 Matemática Discreta Ciências Exatas Engenharias 2o Semestre de 2014 1 Construa a tabela da verdade para a seguinte proposição E p p q q r Resposta p q r p p q q r E V V V V V V V V F V F F V F V V V V V F F V V V F V V V V V F V F V F F F F V V V V F F F V V V 2 Mostre se as expressões E1 e E2 são equivalentes logicamente E1 s p r p r q s E2 p q r s p s Resposta p q r s s p r p r q s E1 p q r s p s E2 V V V V F V F F F F V V V F V F F F F F V V F V V V V V F V V V F F V F F F F F V F V V F V F F F F V F V F V F F F F F V F F V V F F F F F V F F F V F F F F F F V V V F V F F F F F V V F V F F F V V F V F V F V F F F F F V F F V F F F V V F F V V F V F F F F F F V F V F F F V V F F F V F V F F F F F F F F V F F F V V Como as duas tabelas da verdade não são idênticas as expressões E1 e E2 não são equivalentes logicamente 1 3 Faça a simplificação lógica da seguinte expressão usando apenas as leis da lógica p p q p q Resposta p p q p q De Morgan sobre p q p p q p q Associatividade sobre p p q p p q p q Idempotência sobre p p p q p q Distributividade sobre a expressão p q q Negação sobre q q p t Identidade com a tautologia t p 4 Mostre se o seguinte argumento é válido ou não usando as formas válidas de argumentos Em cada passo identifique a razão para se obter a conclusão a p r s b t s c u p d w e u w f t w Resposta Deduções i u w e w d u Silogismo Disjuntivo ii u p c u i p Modus Ponens iii p r s a p ii r s Modus Ponens iv r s iii s Simplificação Conjuntiva v t s b s iv t Modus Tollens vi t v t w Adição Disjuntiva A forma de argumento é válida 5 O famoso detetive Percule Hoirot foi chamado para resolver um assassinato misterioso Ele determinou os seguintes fatos a Lord Charles o homem assassinado foi morto com uma pancada na cabeça com um castiçal 2 b Ou Lady Camila ou a empregada Sara estavam na sala de jantar no momento do assassinato c Se o cozinheiro estava na cozinha no momento do assassinato então o açougueiro matou Lord Charles com uma dose fatal de arsênico d Se Lady Camila estava na sala de jantar no momento do assassinato então o motorista matou Lord Charles e Se o cozinheiro não estava na cozinha no momento do assassinato então Sara não estava na sala de jantar quando o assassinato ocorreu f Se Sara estava na sala de jantar no momento do assassinato então o ajudante pessoal de Lord Charles o matou É possível para o detetive Percule Hoirot deduzir quem matou Lorde Charles Se sim quem é o assassino Resposta Sejam os seguintes argumentos p Lord Charles foi morto com uma pancada na cabeça com um castiçal q Lady Camila estava na sala de jantar no momento do assassinato r Sara estava na sala de jantar no momento do assassinato s Cozinheiro estava na cozinha no momento do assassinato t Açougueiro matou Lord Charles com uma dose fatal de arsênico u Motorista matou Lord Charles v Ajudante pessoal de Lord Charles o matou Tradução dos fatos para as proposições a p b q r c s t d q u e s r f r v Deduções i Suponha que s seja V ie o cozinheiro estava na cozinha no momento do assassinato s t c s Suposição t Modus Ponens ii No entanto t contradição já que Lord Charles não foi morto com arsênico e sim por uma pancada na cabeça a Logo a suposição que o cozinheiro estava na cozinha é falsa Assim temos s s t c t contradição i s Silogismo Hipotético e Contradição iii s r e s ii r Modus Ponens iv q r b r iii q Silogismo Disjuntivo v q u d q iv 3 u Modus Ponens De onde se conclui que o motorista matou Lord Charles 6 Construa a tabela da verdade para a seguinte proposição E p q p q Resposta p q p q p q E V V F V F V F V F F F V V F F F F F V F 7 Construa a tabela da verdade para a seguinte proposição E p q p r Resposta p q r p q r p q p r E V V V F F F V F F V V F F F V V V V V F V F V F F F V V F F F V V F V V F V V V F F F V V F V F V F V F V V F F V V V F V V V F F F V V V V V V 8 Seja a tabela da verdade do operador p q p q V V V V F F F V F F F V a O operador segue a lei da associatividade com o operador ie x y z x y z Resposta x y z x y z x y z V V V V V V V F F F V F V F F V F F F F F V V F F F V F F V F F V V V F F F F V Como as duas colunas da direita não são idênticas o operador não segue a lei da associatividade com o operador b O operador segue a lei da distributividade com o operador ie x y z x y x z Resposta 4 x y z x y z x y x z V V V V V V V F F F V F V F F V F F F F F V V F F F V F V F F F V V F F F F V V Como as duas colunas da direita não são idênticas o operador não segue a lei da distributividade com o operador 9 Mostre a equivalência lógica da seguinte proposição usando apenas as leis da lógica p r q r p q r Resposta p r q r p q r p r q r p q r p q r p q r p q r 10 Mostre se os seguintes requisitos são consistentes ou não Caso sejam para que valores esses requisitos são consistentes Se o sistema de arquivos não está travado então novas mensagens serão enfileiradas Se o sistema de arquivos não está travado então o sistema está funcionando normalmente e viceversa Se novas mensagens não são enfileiradas então elas serão enviadas para o buffer de mensagens Se o sistema de arquivos não está travado então novas mensagens serão enviadas para o buffer de mensagens Novas mensagens não serão enviadas para o buffer de mensagens Resposta Sejam os seguintes argumentos p O sistema de arquivos não está travado q Novas mensagens serão enfileiradas r O sistema está funcionando normalmente s Mensagens serão enviadas para o buffer de mensagens Tradução dos fatos para as proposições a p q b p r c r p d q s e p s f s Deduções i q s d 5 s f q Modus Tollens ii p s e s f p Modus Tollens iii r p c p ii r Modus Tollens iv p r b r iii p Modus Tollens Pelas deduções acima temos que os requisitos são consistentes para os valores p V O sistema de arquivos está travado q V Novas mensagens serão enfileiradas r V O sistema não está funcionando normalmente s V Mensagens não serão enviadas para o buffer de mensagens 11 Mostre se o seguinte argumento é válido ou não p q r p q q p r Resposta Variáveis Aux Premissas Conclusão p q r p q p q r p q q p r 1 V V V F V V V V 2 V V F F V V V F 3 V F V V V V V V 4 V F F V F V V 5 F V V F V V F 6 F V F F V V F 7 F F V F V F V 8 F F F F V F V A conclusão é verdadeira para as linhas 1 e 3 e falsa para a linha 2 Ou seja a conclusão não é verdadeira para todas as linhas críticas Logo o argumento é inválido 12 Mostre se o seguinte argumento é válido ou não usando as formas válidas de argumentos Em cada passo identifique a razão para se obter a conclusão a p q b r s c s t d q s e s f p r u g w t h u w 6 Resposta i r s b s e r Silogismo disjuntivo ii q s d s e q Silogismo disjuntivo iii p q a q ii p Modus Tollens iv p r u f p r Adição conjuntiva de iii e i u Modus Ponens v s t c s e t Modus Ponens vi w t g t v w Silogismo disjuntivo vii u iv w vi u w Adição conjuntiva O argumento é válido 13 Sejam duas variáveis lógicas x e y ou seja variáveis que podem assumir o valor verdadeiro V ou falso F Seja o comando de atribuição existente em linguagens de programação como C e o operador definido no exercício 8 Qual é o valor dessas variáveis ao final da execução sequencial dos três comandos abaixo Apresente a sua resposta independente dos valores iniciais de x e y x x y y x y x x y Resposta Reescrevendo os comandos acima com o operador ou exclusivo temos veja exercício 8 x x y y x y x x y Executando os comandos e lembrando que o operador ou exclusivo segue a lei da associatividade e que 0 é o elemento neutro temos x x y 1 y x y x y y x y y x 0 x 2 x x y x y y x y x x x y 0 y y 3 7 No comando 1 a variável x recebe o resultado de x y No comando 2 a variável y recebe o resultado da operação do ou exclusivo entre a variável x que contém o resultado de xy e a variável y O resultado dessa operação é x No comando 3 a variável x recebe o resultado da operação do ou exclusivo entre a variável x que contém o resultado de x y e a variável y cujo valor é x O resultado dessa operação é y Ou seja após a execução desses três comandos a variável x tem o valor inicial de y e a variável y tem o valor inicial de x O texto a seguir foi retirado do livro texto página 19 Lógicas Fuzzy são utilizadas em inteligência artificial Na lógica fuzzy a proposição tem um valorverdade que é um número entre 0 e 1 inclusive Uma proposição com valorverdade 0 é falsa e uma com valorverdade 1 é verdadeira Valores entre 0 e 1 indicam variantes de grau de verdade Por exemplo o valorverdade 08 pode ser indicado para uma proposição Fred é feliz porque ele é feliz na maior parte do tempo e o valorverdade 04 pode ser indicado para a proposição John é feliz porque ele é feliz menos que a metade do tempo 14 O valorverdade da negação de uma proposição em lógica fuzzy é 1 menos o valorverdade da proposição Quais são os valoresverdade das proposições Fred não é feliz e John não é feliz Resposta pf 0 8 Fred é feliz pj 0 4 John é feliz pf 1 pf 1 0 8 0 2 Fred não é feliz pj 1 pj 1 0 4 0 6 John não é feliz 15 O valorverdade da disjunção de duas proposições em lógica fuzzy é o máximo dos valoresverdade de duas proposições Quais são os valoresverdade das proposições Fred é feliz ou John é feliz e Fred não é feliz ou John não é feliz Resposta Sejam p e q variáveis da Lógica Fuzzy A disjunção p q maxp q a Fred é feliz ou John é feliz pf pj max0 8 0 4 0 8 b Fred não é feliz ou John não é feliz pf pj max0 2 0 6 0 6 16 Cada habitante de uma vila longínqua sempre diz a verdade ou sempre mente Um habitante dela dará apenas como resposta um sim ou um não para a pergunta que um turista fizer Suponha que você seja um turista que visita essa área e que chegue a uma bifurcação na estrada Um lado leva até às ruínas que você quer visitar o outro às profundezas de uma floresta Um habitante dessa vila está parado nessa bifurcação Que pergunta você pode fazer ao habitante para determinar qual lado seguir Resposta Se for perguntado simplesmente qual estrada leva às ruínas e o turista não souber se é um habitante que fala a verdade ou mente então não é possível determinar se a resposta é correta ou não A pergunta não pode depender do tipo de habitante e para isso é necessário formular uma pergunta que envolva duas questões Assim ao invés de perguntar a bifurcação da direita leva às ruínas pergunta P1 que não resolve o problema devese perguntar algo similar a se eu fosse lhe perguntar se a bifurcação da direita me leva às ruínas você responderia sim pergunta P2 Naturalmente a mesma estratégia pode ser feita para a bifurcação da esquerda Veja que a pergunta P2 pode ser vista como se eu fosse lhe perguntar se P1 você responderia sim o que claramente mostra que a pergunta P2 trata de duas questões O habitante que fala a verdade responde corretamente O habitante que fala mentira deve mentir duas vezes no sentido que se a pergunta fosse simplesmente a bifurcação da direita leva às ruínas isto é P1 ele teria que mentir No entanto como há uma segunda questão envolvida se eu fosse lhe perguntar se P1 você responderia sim então esse habitante deve mentir novamente Esse raciocínio está representado na tabela abaixo 8 P1 A bifurcação da direita leva às ruínas P2 Se eu fosse lhe perguntar se a bifurcação da direita me leva às ruínas você responderia sim Tipo de habitante Bifurcação da direita leva às ruínas P1 P2 Fala verdade Sim Sim Sim Não Não Não Fala mentira Sim Não Sim Não Sim Não Se o habitante sempre fala a verdade ele dirá ao turista se deve seguir pela bifurcação da direita ou esquerda Se o habitante sempre fala mentira ao responder a P2 ele sabe que mentiu ao responder P1 parte dessa pergunta No entanto ele mente novamente e no final ele responde corretamente a bifurcação a ser seguida A estratégia é usar uma dupla negativa 17 Este sistema de especificações é consistente O sistema está em um estado de multiuso se e somente se estiver operando normalmente Se o sistema está operando normalmente o núcleo do sistema operacional kernel está funcionando O kernel não está funcionando ou o sistema está no modo de interrupção Se o sistema não está em um estado de multiuso então está em um modo de interrupção O sistema não está no modo de interrupção Resposta Sejam os seguintes argumentos p O sistema está em um estado de multiuso q O sistema está operando normalmente r O núcleo do sistema operacional kernel está funcionando s O sistema está no modo de interrupção Tradução dos fatos para as proposições a p q p q q p b q r c r s d p s e s Deduções i r s c s e r Silogismo Disjuntivo ii q r b r i q Modus Tollens iii p s d s e p Modus Tollens iv p q q p a p q Simplificação Conjuntiva v p q iv q ii 9 p Modus Tollens As conclusões iii e v dizem que p e p devem ser verdadeiros o que claramente é inconsistente 18 Este sistema de especificações é consistente O roteador pode enviar mensagens para o sistema principal somente se ele tratar um novo espaço de endereço Para o roteador tratar o novo espaço de endereço é necessário que a última versão do software seja instalada O roteador pode enviar mensagens ao sistema principal se a última versão do software estiver instalada O roteador não trata o novo espaço Resposta Sejam os seguintes argumentos p O roteador pode enviar mensagens para o sistema principal q O roteador trata um novo espaço de endereço r A última versão do software seja instalada Tradução dos fatos para as proposições a p somente se q p q b para q é necessário r r é uma condição necessária para q q r c p se r r p p r d q Dedução i p q a q d p Modus Tollens ii p r c p i r Modus Ponens Pelas deduções acima as três proposições são falsas q de acordo com d p de acordo com i e r de acordo com ii Se todas três proposições são falsas as quatro especificações são verdadeiras e elas são consistentes 19 Um detetive entrevistou quatro testemunhas de um crime A partir das histórias das testemunhas o detetive concluiu que se o mordomo está dizendo a verdade então o cozinheiro também está o cozinheiro e o jardineiro ambos não podem estar dizendo a verdade o jardineiro e o zelador ambos não estão mentindo e se o zelador está dizendo a verdade então o cozinheiro está mentindo Para cada uma das quatro testemunhas o detetive pode determinar se a pessoa está mentindo ou dizendo a verdade Resposta As quatro testemunhas podem ser identificadas pelas variáveis C cozinheiro J jardineiro M mordomo e Z zelador que serão usadas para indicar que estão falando a verdade Sejam os seguintes argumentos a M C se o mordomo está dizendo a verdade então o cozinheiro também está b C J o cozinheiro e o jardineiro ambos não podem estar dizendo a verdade c J Z o cozinheiro e o jardineiro ambos não podem estar dizendo a verdade d Z C se o zelador está dizendo a verdade então o cozinheiro está mentindo Pelos quatro argumentos acima não é possível aplicar uma regra de inferência Se fizermos uma tabela da verdade podemos identificar o cenário no qual as quatro premissas supostamente são verdadeiras conforme mostrado a seguir 10 Variáveis Premissas C J M Z a b c d 1 V V V V V F F F 2 V V V F V F V V 3 V V F V V F F F 4 V V F F V F V V 5 V F V V V V V F 6 V F V F V V F V 7 V F F V V V V F 8 V F F F V V F V 9 F V V V F V F V 10 F V V F F V V V 11 F V F V V V F V 12 F V F F V V V V 13 F F V V F V V V 14 F F V F F F F V 15 F F F V V F V V 16 F F F F V F F V As premissas são verdadeiras para a linha 12 ou seja o jardineiro fala a verdade e as outras testemunhas não O texto a seguir foi retirado do livro texto página 29 O dual de uma proposição composta que contém apenas os operadores lógicos e é a proposição composta obtida pela troca de cada por cada por cada V por F e cada F por V O dual de s é representado por s 20 Encontre o dual de cada uma das seguintes proposições compostas a s1 p q r Resposta s 1 p q r b s2 p q r s Resposta s 2 p q r s c s3 p F q V Resposta s 3 p V q F d Apresente um exemplo de proposição composta formada por pelo menos duas variáveis tal que s s Resposta s4 p F q V p V p s 4 p V q F p F p 11