Lista de Exercícios Resolvidos - Lógica Proposicional 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 φ