Lista de Exercícios Lógica Matemática - Proposições e Funções de Verdade

1 A resposta desta questão é a soma das afirmações verdadeiras 1 A B C A B A C 2 A A A 4 A A B A 2 A resposta desta questão é a soma das afirmações verdadeiras 1 A B sse A B 2 A B sse A e B 4 Se existe s tal que s A então A não é uma tautologia 3 A resposta desta questão é a soma das afirmações verdadeiras 1 A B A B 2 A B A B 4 φ ψ ψ φ 4 A resposta desta questão é a soma das afirmações verdadeiras 1 Assuma que n é o símbolo repetido n vezes Então 3 é Podemos afirmar que 1001 A B B A 2 O contradomínio de uma função de verdade de uma fórmula φ com 10 variáveis é V F 4 A imagem de uma função de verdade de uma fórmula φ com 10 variáveis pode ser apenas V 5 A resposta desta questão é a soma das afirmações verdadeiras 1 A A φ para qualquer φ 2 A2 é consequência lógica de A1 A2 An com n 5 4 A2 A5 é consequência lógica de Ai Aj sendo n 3 e m 7 8 Já que eu sempre fico cansado quando faço exercícios físicos então se estou cansado é porque fiz exercícios físicos 6 A resposta desta questão é a soma das afirmações verdadeiras Se s φ e s ψ então 1 s φ ψ 2 s ψ φ 4 s φ ψ 8 s φ ψ 7 A resposta desta questão é a soma das afirmações verdadeiras 1 A tabela verdade da fórmula φ A B C tem exatamente um valor verdade na coluna de resultados Isto é há uma única sequência s tal que s φ 2 Se uma fórmula φ usa 3 variáveis 1 então o domínio de fφ é V F 4 O contradomínio de todas as funções de verdade é o mesmo para o CP 8 A resposta desta questão é a soma das afirmações verdadeiras Assuma que todas as fórmulas desta questão tenham 5 variáveis e que todas as sequências sejam 5tuplas Seja φ o número de sequências diferentes tal que s φ Baseado nisto responda 1 Se φ 16 é mais fácil construir uma fórmula na FND do que uma na FNC que seja equivalente a φ 2 Se φ ψ 32 então necessariamente existe uma sequência s tal que s φ ψ 9 A resposta desta questão é a soma das afirmações verdadeiras 1 As fórmulas φ e ψ são tais que fφs fψs para todo s s que pode ser usado com estas fórmulas obviamente Então φ ψ 2 As fórmulas φ e ψ usam cinco variáveis cada uma que são A B C D e E Temos que fφs fψs para todo s exceto s V F F V F Então φ ψ A B C D E 4 Se φ então φ V0 8 Duas contradições são sempre lógicamente equivalentes entre si 10 A resposta desta questão é a soma das afirmações verdadeiras Considere que todas as fórmulas utilizadas nesta questão foram construídas usando o algoritmo dado na apostila para a construção de fórmulas na FND baseadas em uma TV 1 φ pode possuir 103 literais e usar 5 variáveis 2 φ pode ter o mesmo número de literais símbolos e que uma fórmula ψ e mesmo assim φ ψ 4 φ pode ter 130 símbolos sendo que existem apenas 128 sequências s tal que fφs V Considere apenas sequências s com o mesmo tamanho que o número de variáveis de φ 8 φ pode ter 1281 símbolos sendo que existem apenas 128 sequências s tal que fφs F Considere apenas sequências s com o mesmo tamanho que o número de variáveis de φ 1 A resposta desta questão é a soma das afirmações verdadeiras 1 A B C A B A C 2 A A A 4 A A B A 2 A resposta desta questão é a soma das afirmações verdadeiras 1 A B sse A B 2 A B sse A e B 4 Se existe s tal que s A então A não é uma tautologia 3 A resposta desta questão é a soma das afirmações verdadeiras 1 A B A B 2 A B A B 4 φ ψ ψ φ 4 A resposta desta questão é a soma das afirmações verdadeiras 1 Assuma que n é o símbolo repetido n vezes Então 3 é Podemos afirmar que 1001 A B B A 2 O contradomínio de uma função de verdade de uma fórmula φ com 10 variáveis é V F 4 A imagem de uma função de verdade de uma fórmula φ com 10 variáveis pode ser apenas V 5 A resposta desta questão é a soma das afirmações verdadeiras 1 A A φ para qualquer φ 2 A2 é consequência lógica de A1 A2 An com n 5 4 A2 A5 é consequência lógica de Ai Aj sendo n 3 e m 7 8 Já que eu sempre fico cansado quando faço exercícios físicos então se estou cansado é porque fiz exercícios físicos 6 A resposta desta questão é a soma das afirmações verdadeiras Se s φ e s ψ então 1 s φ ψ 2 s ψ φ 4 s φ ψ 8 s φ ψ 7 A resposta desta questão é a soma das afirmações verdadeiras 1 A tabela verdade da fórmula φ A B C tem exatamente um valor verdade na coluna de resultados Isto é há uma única sequência s tal que s φ 2 Se uma fórmula φ usa 3 variáveis 1 então o domínio de fφ é V F 4 O contradomínio de todas as funções de verdade é o mesmo para o CP 8 A resposta desta questão é a soma das afirmações verdadeiras Assuma que todas as fórmulas desta questão tenham 5 variáveis e que todas as sequências sejam 5tuplas Seja φ o número de sequências diferentes tal que s φ Baseado nisto responda 1 Se φ 16 é mais fácil construir uma fórmula na FND do que uma na FNC que seja equivalente a φ 2 Se φ ψ 32 então necessariamente existe uma sequência s tal que s φ ψ 9 A resposta desta questão é a soma das afirmações verdadeiras 1 As fórmulas φ e ψ são tais que fφs fψs para todo s s que pode ser usado com estas fórmulas obviamente Então φ ψ 2 As fórmulas φ e ψ usam cinco variáveis cada uma que são A B C D e E Temos que fφs fψs para todo s exceto s V F F V F Então φ ψ A B C D E 4 Se φ então φ V0 8 Duas contradições são sempre lógicamente equivalentes entre si 10 A resposta desta questão é a soma das afirmações verdadeiras Considere que todas as fórmulas utilizadas nesta questão foram construídas usando o algoritmo dado na apostila para a construção de fórmulas na FND baseadas em uma TV 1 φ pode possuir 103 literais e usar 5 variáveis 2 φ pode ter o mesmo número de literais símbolos e que uma fórmula ψ e mesmo assim φ ψ 4 φ pode ter 130 símbolos sendo que existem apenas 128 sequências s tal que fφs V Considere apenas sequências s com o mesmo tamanho que o número de variáveis de φ 8 φ pode ter 1281 símbolos sendo que existem apenas 128 sequências s tal que fφs F Considere apenas sequências s com o mesmo tamanho que o número de variáveis de φ Problema 1 Resposta 1 Observe que A B C pela lei da associatividade é A B C A B C A B A C 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 Tabela 1 Tabela da Verdade da Expressão Como podemos ver as funções não são equivalentes portanto a pri meira afirmação é falsa 2 Verdeiro pois se A então A é verdade e assim A A 3 Observe a tabela a seguir A B A A B A 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 Tabela 2 Tabela da Verdade da Expressão Assim a expressão é verdadeira Logo o valor da questão é 6 Problema 2 Resposta A resposta correta é a afirmação 2 AB se e somente se AB 1 A B se e somente se A B Essa afirmação está correta A relação satisfatibilidade entre duas fórmulas implica na relação dedução lógica entre elas quando A implica logicamente B Portanto se A B então A B 3 2 2 A B se e somente se A e B Essa afirmação está correta Se a conjunção AB é satisfeita em um modelo isso implica que tanto A quanto B são satisfeitas individualmente nesse modelo Da mesma forma se A e B são satisfeitas em um modelo então a conjunção AB também é satisfeita nesse modelo Portanto A B se e somente se A e B 4 Se existe s tal que s A então A não é uma tautologia Essa afirmação está correta Se encontrarmos um modelo s em que a fórmula A não é satisfeita s A isso significa que A não é verdadeira em todos os modelos possíveis Portanto A não é uma tautologia Portanto a soma das afirmações verdadeiras é 1 2 4 Problema 3 Resposta Vamos analisar cada uma das afirmações e determinar quais delas são verdadeiras 1 A B A B Para verificar a validade dessa afirmação precisamos verificar se as duas condições são equivalentes A equivalência lógica é determinada pela tabela de verdade da implicação lógica A tabela de verdade para A B é A B A B V V V V F F F V V F F V A tabela de verdade para A B é Podemos observar que as duas A B A B V V V V F F F V F F F V tabelas de verdade não são idênticas Portanto a afirmação 1 não é verdadeira 4 2 ABAB Vamos analisar a equivalência dessa afirmação usando a tabela de ver dade A tabela de verdade para AB é A B A B V V F V F F F V F F F V A tabela de verdade para A B é Podemos observar que as duas A B A B V V F V F F F V F F F V tabelas de verdade são idênticas Portanto a afirmação 2 é verda deira 4 ϕ ψ ψ ϕ Vamos analisar a equivalência dessa afirmação usando a tabela de ver dade A tabela de verdade para ϕ ψ é ϕ ψ ϕ ψ V V V V F F F V F F F V A tabela de verdade para ψ ϕ é Podemos observar que as duas tabelas de verdade são idênticas Portanto a afirmação 4 é verda deira 5 ϕ ψ ψ ϕ V V V V F F F V F F F V Conclusão Das três afirmações apresentadas apenas as afirmações 2 e 4 são verdadeiras Portanto a resposta para o problema é a soma das afirmações verdadeiras ou seja 2 4 Problema 4 Resposta 1 Assuma que n é o símbolo repetido n vezes Então 3 é Podemos afirmar que 100 1 A B B A Essa afir mação é verdadeira Ela introduz a notação de repetição do símbolo de negação para representar uma negação múltipla A equivalência 100 1 A B B A também é uma propriedade válida da lógica conhecida como Lei de De Morgan 2 O contradomínio de uma função de verdade de uma fórmula ϕ com 10 variáveis é V F Essa afirmação é verdadeira O contradomínio de uma função de verdade é o conjunto de valores possíveis para a fórmula ϕ No caso de uma fórmula com 10 variáveis cada variável pode assumir dois valores verdadeiro ou falso portanto o contradomínio será o conjunto V F 4 A imagem de uma função de verdade de uma fórmula ϕ com 10 variá veis pode ser apenas V Essa afirmação é falsa A imagem de uma função de verdade de uma fórmula com 10 variáveis pode incluir tanto o valor verdadeiro V como o valor falso F dependendo da fórmula específica e das combinações de valores atribuídos às variáveis Portanto a soma das afirmações verdadeiras é 1 e 2 e a afirmação 4 é falsa Problema 5 Resposta A resposta desta questão é a soma das afirmações verdadeiras 1 Verdadeiro A afirmação é uma aplicação direta da regra de inclusão disjuntiva na lógica proposicional 6 2 Falso A afirmação não é verdadeira em geral A consequência lógica não é uma relação transitiva portanto não podemos afirmar que A2 é consequência lógica de A1 A2 An apenas com base no número de variáveis 4 Falso A afirmação não é verdadeira em geral A relação de consequência lógica não depende apenas do número de variáveis e não podemos inferir que A2 A5 é consequência lógica de Ai Aj com base nas condições dadas 8 Verdadeiro A afirmação é uma aplicação direta da regra de implicação na lógica proposicional Portanto a soma das afirmações verdadeiras é 1 e 8 Problema 6 Resposta A resposta desta questão é a soma das afirmações verdadeiras Se s ϕ e s ψ então 1 Verdadeiro A afirmação s ϕ ψ é verdadeira porque se s é um modelo que satisfaz ϕ e não satisfaz ψ então s também satisfaz a conjunção ϕ ψ 2 Falso A afirmação s ψ ϕ é falsa porque mesmo que s satisfaça ϕ e não satisfaça ψ não podemos concluir que a implicação ψ ϕ é verdadeira para todos os modelos s 4 Falso A afirmação s ϕ ψ é falsa porque embora s satisfaça ϕ e não satisfaça ψ não podemos concluir que a implicação ϕ ψ é verdadeira para todos os modelos s 8 Verdadeiro A afirmação s ϕ ψ é verdadeira porque se s é um modelo que satisfaz ϕ e não satisfaz ψ então s também satisfaz a conjunção ϕ ψ Portanto a soma das afirmações verdadeiras é 1 e 8 Problema 7 Resposta A resposta desta questão é a soma das afirmações verdadeiras 1 Verdadeiro A tabela verdade da fórmula ϕ A B C tem exatamente um valor verdade na coluna de resultados Isso significa que há uma única sequência s tal que s ϕ 2 Falso Se uma fórmula usa 3 variáveis 1 então o domínio de fϕ não é necessariamente V F O domínio depende das combinações possíveis das variáveis 1 4 Falso O contradomínio das funções de verdade pode variar depen dendo do contexto Não é necessariamente o mesmo para o Cálculo Proposicional CP como um todo Portanto a soma das afirmações verdadeiras é 1 Problema 8 Resposta A resposta desta questão é a soma das afirmações verdadeiras Assuma que todas as fórmulas desta questão tenham 5 variáveis e que todas as sequências sejam 5tuplas Seja ϕ o número de sequências diferentes tal que s ϕ Baseado nisto responda 1 Verdadeiro Se ϕ 16 é mais fácil construir uma fórmula na Forma Normal Disjuntiva FND do que uma na Forma Normal Conjuntiva FNC que seja equivalente a ϕ Isso ocorre porque na FND é mais simples listar todas as sequências que satisfazem ϕ do que listar todas as sequências que não satisfazem ϕ na FNC 2 Falso A afirmação não é necessariamente verdadeira Se ϕ ψ 32 isso não implica necessariamente que existe uma sequência s tal que s ϕ ψ A existência de tal sequência depende das combinações das variáveis em ϕ e ψ Portanto a soma das afirmações verdadeiras é 1 Problema 9 Resposta A resposta desta questão é a soma das afirmações verdadeiras 1 Verdadeiro Se as fórmulas ϕ e ψ têm a mesma tabela de verdade para todas as atribuições possíveis das variáveis então ϕ é logicamente equivalente a ψ Isso significa que ϕ ψ 2 Falso A afirmação não é necessariamente verdadeira Se as fórmulas ϕ e ψ têm a mesma tabela de verdade para todas as atribuições exceto uma isso não implica necessariamente que ϕ ψ A B C D E A fórmula indicada na afirmação não é necessariamente verdadeira para todas as atribuições 8 4 Verdadeiro Se ϕ isso significa que ϕ é uma tautologia ou seja é verdadeira para todas as atribuições possíveis das variáveis Nesse caso também temos que ϕ V0 onde V0 é uma fórmula sempre verdadeira 8 Verdadeiro Duas contradições são sempre logicamente equivalentes entre si Isso ocorre porque uma contradição é uma fórmula que é sempre falsa independentemente das atribuições das variáveis Portanto a soma das afirmações verdadeiras é 1 e 4 Problema 10 Resposta 9