Baixe o app para aproveitar ainda mais
Prévia do material em texto
Departamento de Computação Introdução à Lógica Lucia Helena Machado Rino Introdução à Lógica Exercícios de Cálculo Proposicional Lucia Helena Machado Rino Você tem aqui exercícios genéricos do Cálculo Proposicional separados por temas e grau de dificuldade. Uma das seções é só sobre as propriedades desse formalismo. Recorra a ela sempre que os exercícios das outras seções demandarem o uso de propriedades. 2 Exercicios-CalcPropos Sintaxe do Cálculo Proposicional 1. Dê exemplos de sentenças bem formadas1 em português, independentemente de elas serem verdadeiras ou falsas. 2. Construa fbfs a partir de suas sentenças da questão anterior, usando a linguagem do Cálculo Proposicional. 3. Os conectivos do conjunto {¬,∨,↔,∧,�} fazem parte da linguagem do Cálculo Proposicional? 4. Remova o maior número possível de parênteses das seguintes fórmulas2: 4.1. (((α ∧ β) � (¬(β) � (β � α))) ∧ γ) 4.2. (¬α � (β ∧ γ)) ↔ (((α ∧ β) ∨ γ) ↔ α) 4.3. (α ∧ β) ∧ γ 4.4. (α ∨ γ) ↔ (α � ¬β) 4.5. ({[(p ∨ ¬q) ∨ r] ∧ [p ∨ ¬ (¬q)]} ∧ ¬r) 4.6. ((p � ¬ (q ∨ r)) � (¬p� ¬q)) 5. Quais sentenças abaixo são fbfs do Cálculo Proposicional? 5.1. ¬¬¬¬ α � α ∧ ¬ α 5.2. ↔∧ αβα 5.3. ∨∧ αβα 5.4. ((β � α) ∨ α 6. Responda: 6.1. O que é a sintaxe de uma linguagem? 6.2. Do que trata a sintaxe do Cálculo Proposicional? 6.3. Por que é importante construir fbfs? 7. Diga quais das seguintes expressões são formas sentenciais e, para essas, diga quais são os conectivos principais. 7.1. (((α ∨ ¬β) � α) ∧ ¬α) 7.2. ((((α � β) � α) � α) ∨ β) 7.3. ¬ (((α ∨ β) ∨ γ ) ↔ ¬β) 8. Traduzir para a linguagem do Cálculo Proposicional as seguintes proposições em português: 8.1. “Marcos é alto e elegante.” 8.2. “Marcos é alto, mas não é elegante.” 8.3. “Não é verdade que Marcos é baixo ou elegante.” 8.4. “Marcos não é alto e nem elegante.” 8.5. “Marcos é alto ou baixo e elegante.” 8.6. “É falso que Marcos é baixo ou que não é elegante.” 9. Responda, justificando: 9.1. “Marcos é deselegante.” poderia ser outra proposição no conjunto de proposições da questão anterior? 9.2. Se ela fosse outra proposição no mesmo conjunto, ela teria equivalência sintática com a proposição “Marcos não é elegante.”? 1 Sentenças bem formadas são proposições sintaticamente corretas, de acordo com a gramática da linguagem proposicional. São também chamadas formas sentenciais ou fórmulas bem formadas, sendo este o termo preferencial neste curso. Serão representadas pela sigla fbf. 2 Na parentização, é possível usar os demais símbolos delimitadores clássicos de colchetes ou chaves, além dos parênteses. 3 Exercicios-CalcPropos Semântica do Cálculo Proposicional 10. Construa sentenças que sejam verdadeiras ou falsas com base em seu conhecimento de mundo. 11. Construa sentenças que não sejam verdadeiras nem falsas com base em seu conhecimento de mundo. 12. Prove as seguintes afirmações: 12.1. Uma fbf é inconsistente se e somente se sua negação for válida. 12.2. Uma fbf é inválida se e somente se existir pelo menos uma interpretação em que ela é falsa. 12.3. Uma fbf é consistente se e somente se existir pelo menos uma interpretação em que ela é verdadeira. 12.4. Se uma fbf for válida, então ela será consistente, mas não vice-versa. 12.5. Se uma fbf for inconsistente, então ela será inválida, mas não vice-versa. 13. Verifique as seguintes afirmações usando a TV3: 13.1. p ∧ ¬p é inconsistente e, portanto, inválida. 13.2. p ∨ ¬p é válida e, portanto, consistente. 13.3. p � ¬p é inválida, ainda que consistente. 14. Simplifique as expressões abaixo utilizando as propriedades conhecidas do Cálculo Proposicional, especificando-as em cada passo. 14.1. ¬ (p ∧ ¬q) ∨ (q ∧ r) 14.2. (p ∨ q ∨ r) ∧ ¬ (p ∧ ¬q ∧ ¬r) ∧ ¬r 15. Mostre que os parênteses são necessários para escrever expressões que resolvam mais de uma das operações de disjunção (∨) e conjunção (∧). Sugestão: Considere A ∧ B ∨ C e veja como ele pode ser interpretado com e sem os parênteses. 16. Prove que: 16.1. (α ∨ β) ∧ ¬α ⇔ β ∧ ¬α 16.2. (α ∨ β) ∧ β ⇔ β 17. Simplificar as seguintes proposições: 17.1. (p � q) ∧ (¬p � q) 17.2. p ∧ (p � q) ∧ (p � ¬q) 17.3. (p ∨ q) ∧ ¬p 17.4. ¬ (¬p ∧ q) 18. Prove a regra da exportação-importação: p � (q � r) ⇔ p ∧ q � r 19. Mostre a equivalência entre as expressões dadas abaixo: 19.1. (p ↔ (p ∧ ¬p) ) ⇔ ¬ p 19.2. [ (p � q) � (q � r) ] ⇔ (q � r) 20. Mostre que “A é logicamente equivalente a B se e só se A implica logicamente B e B implica logicamente A”, isto é, α ↔ β se e só se α � β ∧ β � α4 21. É verdade que x ∨ ¬y ⇔ (x ∨ y ∨ ¬z) (x ∨ ¬y ∨ ¬z)? Justifique sua resposta. 22. Demonstre, sem usar indução perfeita, se cada uma das seguintes equações é válida: 22.1. (x ∨ y) (¬x ∨ y) (x ∨ ¬y) (¬x ∨ ¬y) = false 22.2. xy ∨ ¬x ¬y∨ x¬yz ⇔ xz ∨ ¬x ¬y ∨ ¬xyz 23. Sabendo-se que as meta-variáveis proposicionais p e q são verdadeiras e r e s são falsas, interprete logicamente cada uma das seguintes formas sentenciais: 3 Método chamado indução perfeita: prova de um teorema para todas as combinações possíveis de valores que suas variáveis podem assumir. 4 Atenção: neste exercício, é preciso pensar no teorema T2, relacionado à veracidade da bicondicional quando A ⇔ B. 4 Exercicios-CalcPropos 23.1. ¬ ((¬r ∨ p) ∨ (¬s ∨ q)) 23.2. ¬r ⇒ p ∧ q 23.3. ¬ (((p ∨ q) ∨ r) ⇔ ¬s) 24. Considerando a proposição do exercício 9 acima – “Marcos é alto ou baixo e elegante.” – e seu conhecimento de mundo, 24.1. Use os 3 átomos implicitamente representados nessa proposição composta para mostrar qual a prioridade correta entre os conectivos dessa proposição. 24.2. A disjunção dessa proposição é exclusiva? Justifique. 24.3. Sua veracidade depende da disjunção? Justifique a partir da formulação lógica da sentença no CalcProposic e de propriedades de simplificação. Propriedades do Cálculo Proposicional 25. Verificar os exercícios sugeridos pela prof. Carmo na apostila de CalcProposic, p. 14 e 15 26. Prove, usando axiomas (definições) e a regra dedutiva Modus ponens5, quando aplicável, que: 26.1. α ⇒ α 26.2. α � β, β � γ e α � γ constituem um argumento, isto é, (α � β) ∧ (β � γ) ⇒ α � γ 26.3. ((α � (¬α � α)) � ((α � ¬α) � (α � α))) 26.4. ((α � β) � α) ⇒ α 26.5. α ⇒ (β � (α ∧ β)) 27. Dada a fórmula α � β, 27.1. Podemos dizer que α implica logicamente β? 27.2. Podemos dizer que α é logicamente equivalente a β? 28. Prove que, se α e α� β são tautologias, então β é tautologia. 29. Qual o princípio que garante que, se α� β ⇔ ¬α ∨ β, então γ ∧ ((α� β) ↔ γ) ⇔ γ ∧ ((¬α ∨ β) ↔ γ)? 30. Encontre uma FND logicamente equivalente a uma das fbfs do exercício anterior. 31. Quais das fbfs abaixo estão em sua FNC ou FND? 31.1. ¬α ∧ β ∨ γ ∧ α 31.2. ¬¬α ∧ β ∨ ¬β ∧ γ 31.3. ¬α ∧ β 31.4. α ∨ ¬β 32. Encontre uma FND que expresse bem a expressão cujos valores-verdade são dados pela seguinte tabela: αααα ββββ γγγγ ? v v v v v v f f v f v v f v v v f v f f v f f f f f v v f f f v 33. Prove que ¬(β1 ∨ β2 ∨ ... ∨ βn) é logicamente equivalente a ¬β1 ∧ ¬β2 ∧...∧ ¬βn usando indução finita em n.6 5 Vários exercícios sugeridos aqui foram extraídos ou modificados de listas de exercícios de José Oliveira ou Maria do Carmo Nicoletti (DC/UFSCar). 5 Exercicios-CalcPropos 34. Encontre uma FND e uma FNC correspondentes à seguinte tabela-verdade: αααα ββββ ? v v vv f f f v f f f v 35. Verificar quais das fbfs seguintes são tautológicas: 35.1. ((p ∧ q) ∧ r) ↔ p ∧ (q ∧ r)) 35.2. ((p ∨ q) ∨ r) ↔ p ∨ (q ∨ r)) 35.3. p ∧ p ↔ p 35.4. p ∨ p ↔ p 35.5. p � p ∨ r Deduções no Cálculo Proposicional 36. Considere uma interpretação I e as seguintes fbfs: α = (p � q); β = (p ↔ q); γ = ¬p ∨ p Responda: 6 Na prova por indução finita, prova-se para n = 2; depois admite-se a hipótese de que vale para n-1 termos e prova-se que vale para n termos. 36.1. Se I(α) = v, o que se pode concluir sobre I(p) e I(q)? 36.2. Se I(β) = v, o que se pode concluir sobre I(p) e I(q)? 36.3. Se I(γ) = v, o que se pode concluir sobre I(p) e I(q)? 36.4. Se I(α) = f, o que se pode concluir sobre I(p) e I(q)? 36.5. Se I(β) = f, o que se pode concluir sobre I(p) e I(q)? 36.6. Se I(γ) = f, o que se pode concluir sobre I(p) e I(q)? 36.7. Se I(q) = v, o que se pode concluir sobre I(α),I(β) e I(γ)? 36.8. Se I(p) = v, o que se pode concluir sobre I(α),I(β) e I(γ)? 37. Seja I uma interpretação tal que I(p� q) = f e J uma interpretação tal que J(p � q) = v. O que se pode deduzir a partir das interpretações a seguir? 37.1. I[ (p ∨ r � (q ∨ r) ] 37.2. I[ (p ∧ r � (q ∧ r) ] 37.3. I[ (¬p ∨ p � (q ∨ p) ] 37.4. J[ (p ∨ r � (q ∨ r) ] 37.5. J[ (p ∧ r � (q ∧ r) ] 37.6. J[ (¬p ∨ p � (q ∨ p) ] 38. Determinar I(p) e I(q) sabendo-se que: 38.1. I(p�q) = v e I(p ∧ q) = f 38.2. I(p↔q) = f e I(¬p ∨ q) = v 39. Identificar os átomos, construir os argumentos correspondentes e identificar a validade das seguintes proposições: 39.1. Se Deus existe, então a vida tem significado. Deus existe. Portanto, a vida tem significado. 39.2. Deus não existe. Se ele existisse, a vida teria significado. A vida não tem significado. 39.3. Como hoje não é quinta-feira, deve ser sexta-feira. Hoje é quinta-feira ou sexta-feira. 39.4. Se hoje for quinta-feira, amanhã será sexta-feira. Se amanhã for sexta-feira, então depois de amanhã será sábado. Logo, se hoje for quinta-feira, depois de amanhã será sábado. 40. Provar, usando regras de inferência e substituição, que os seguintes argumentos são válidos: 40.1. α ⇒ β � α 40.2. ¬α � (β � γ), ¬α, β ⇒ γ 40.3. ¬α � ¬¬β, ¬¬¬α ⇒ β 40.4. α ⇒ α ∨ α 40.5. α ⇒ (α ∨ β) ∧ (α ∨ γ) 40.6. α � β, α � β � (β�α)⇒ α ↔ β Departamento de Computação Introdução à Lógica Lucia Helena Machado Rino 41. Verifique quais dos enunciados são verdadeiros, justificando: 41.1. ¬(p ∧ q) ∨ q é contradição 41.2. p ↔ q ∧ ¬p ↔ ¬q é contradição 41.3. Se p for falso, então q ⇔ ¬p ∨ q 42. A idéia de se usar a linguagem proposicional é reproduzir formalmente, numa linguagem “controlada”, proposições do mundo real. Há uma incidência significativa de condições em nosso mundo. Supondo que cada uma das proposições abaixo tenha uma interpretação verdadeira, pede-se7: 42.1. Indique quais delas expressam condicionais 42.2. Discuta a veracidade de suas respectivas recíprocas 42.3. Discuta a veracidade de suas respectivas contrárias 42.4. Ache as proposições contrapositivas correspondentes e discuta sua veracidade. 42.5. Vimos que uma proposição contrária é equivalente à sua recíproca e uma condicional, à sua contrapositiva. Isso se aplica aos exemplos dados? Justifique sua resposta. P1: Quem tudo olha quase nada enxerga. P2: Quem não quebra se enverga a favor do vento. P3: Quem faz acordo não tem inimigo. P4: Pra quem é pobre a lei é dura. P5: Qualquer dia eu morro de um acesso só por ver o teu processo de iludir os coronéis. P6: Qualquer dia eu perco a paciência, digo uma inconveniência e depois te meto os pés. P7: Devagar com o andar que o santo é de barro. P8: Casa onde não há pão, todos gritam e ninguém tem razão. 43. Seguindo o exemplo do exercício anterior, pede-se 43.1. Ache outras proposições de seu mundo real 43.2. Formule-as na linguagem do CalcProposic 43.3. Indique possíveis equivalências com outras proposições lógicas, usando seu conhecimento dos postulados e propriedades de equivalência. 7 Exemplos extraídos do CD 1º. Compasso: P1-P3 da Faixa 4 (“De qualquer maneira”, Ary Barroso e Noel Rosa); P4-P6 da Faixa 6 (“Nunca...jamais”, Noel Rosa); P7 e P8, respectivamente, dito popular e dito de origem rural (Língua Portuguesa – Especial No. 2 – Etimologia).
Compartilhar