Prova de Lógica para Computação UFPE - Análise e Resolução de Questões

Universidade Federal de Pernambuco UFPE Centro de Informática CIn Lógica para Computação 20212 Prova 1 03 de Março de 2022 LÓGICA ARISTOTÉLICA 1 20 Classifique cada um dos seguintes argumentos como i seguramente válido com premissas consistentes ii válido por vacuidade ou iii inválido Justifique sua resposta Todo A é B Algum A é C Nenhum C é B Logo Algum A não é B Se Algum A é C E Nenhum C é B então Algum A não é B Se Algum A não é B E Todo A é B então há um absurdo entre as premissas Argumento válido por vacuidade Algum A não é B Todo C é B Algum C é A Logo Algum A não é C Se Todo C é B E Algum A não é B então Algum A é C Argumento válido Todo A é B Todo B é C Algum C não é A Logo Algum B não é C Se Todo B é C Não é possível chegar à conclusão de que Algum B não é C Argumento Inválido SINTAXE DA LÓGICA PROPOSICIONAL 2 25 Defina o conjunto de expressões aritméticas com oposto soma e multiplicação como um fecho indutivo de modo que seja um conjunto livremente gerado Justifique sua construção explicando por que é conjunto livremente gerado Σ 0 1 2 3 x X 0 1 2 3 Σ F f f f x f Σ Σ f expr expr e f ΣxΣ Σ f expr 1 expr 2 expr 1 expr 2 x X 0 X X n1 X n U f expr f expr 1 expr 2 f x expr 1 expr 2 Σ expr expr 1 expr 2 X n X X i 𝑖 0 3 15 Sejam posto Ф e par Ф as funções recursivas sobre PROP que retorna o posto da árvore e o número de parênteses respectivamente Defina as funções mencionadas e prove por indução que par Ф 2 posto Ф1 2 posto PROP N postoФ 0 se Ф é átomo postoФ postoΨ 1 se Ф é Ψ postoФ maxpostoΨ postoӨ 1 se Ф é ΨӨ e V par PROP N parФ 0 se Ф é átomo parФ parΨ 2 se Ф é Ψ parФ parΨ parӨ 2 se Ф é ΨӨ e V TESE parФ 2 postoФ1 2 I caso base se Ф é átomo parФ 2 postoФ1 2 0 2 01 2 0 2 2 0 0 ok II primeiro passo indutivo se Ф é Ψ HIPÓTESE INDUTIVA parΨ 2 postoΨ1 2 parΨ 2 postoΨ1 2 parΨ 2 2 postoΨ1 2 2 parФ 2 postoФ parФ 2 postoФ 22 postoФ 1 para todo postoФ 1 parФ 2 postoФ1 2 ok III segundo passo indutivo se Ф é ΨӨ HIPÓTESES INDUTIVAS parΨ 2 postoΨ1 2 e parӨ 2 postoӨ1 2 parΨ 2 postoΨ1 2 parӨ 2 postoӨ1 2 parӨ parΨ 2 postoΨ1 2 postoӨ1 4 parӨ parΨ 2 2 postoΨ1 2 postoӨ1 4 2 parФ 2 maxpostoΨ postoӨ1 1 2 minpostoΨ postoӨ1 2 como 1 12 minpostoΨ postoӨ1 2 então parФ 2 maxpostoΨ1 postoӨ1 1 2 minpostoΨ postoӨ1 2 e 2 maxpostoΨ postoӨ1 1 2 minpostoΨ postoӨ1 2 2 maxpostoΨ postoӨ11 2 logo parФ 2 maxpostoΨ postoӨ11 2 parФ 2 postoФ1 2 ok SEMÂNTICA DA LÓGICA PROPOSICIONAL 4 20 Responda V ou F para as seguintes afirmações Justifique sua resposta V Seja Ф 1 V A Λ B Λ Substituindo por B não importa por quem substituamos a fórmula será insatisfatível se B então Ф 1 V A B Λ B Λ como 1 V A 1 então 1 B Λ B Λ 1 B Λ B Λ 1 B Λ B Λ como B Λ B 0 então 1 0 Λ como 0 Λ 0 então 1 0 e 1 0 0 Logo se B então Ф 0 independente de quem seja o que quer dizer que é insatisfatível V a função binária definida pela tabelaverdade abaixo compõe unicamente um conjunto de operadores funcionalmente completo A B AB 0 0 1 0 1 1 1 0 1 1 1 0 A B A AVB AΛB AB 0 0 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 1 1 0 1 1 1 A B AA AABB ABAB ABA 0 0 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 1 1 0 1 1 1 5 20 Prove que se Γ ФΨ então Γ U Ф Ψ I se Γ ФΨ então Γ U ФΨ é insatisfatível 1 se Γ ФΨ então toda valoração que satisfaz Γ torna ФΨ verdadeira 2 então toda valoração que satisfaz Γ torna ФΨ falsa 3 então Γ U ФΨ é insatisfatível II Γ U ФΨ é insatisfatível Γ U Ф Ψ é insatisfatível 4 seja Γ Ψ 1 Ψ n se Γ U ФΨ é insatisfatível então qualquer valoração torna Ψ 1 Λ ΛΨ n ΛФΨ falsa 5 como ФΨ ФVΨ ФΛΨ então qualquer valoração torna Ψ 1 Λ ΛΨ n ΛФΨ torna Ψ 1 Λ ΛΨ n ΛФΛΨ 6 então Ψ 1 Ψ n Ф Ψ Γ U Ф Ψ é insatisfatível III se Γ U Ф Ψ é insatisfatível então Γ U Ф Ψ 7 se Γ U Ф Ψ é insatisfatível então não há valoração que satisfaça se Γ Ф e Ψ ao mesmo tempo 8 então i ou há contradição entre as fórmulas Γ ii ou há contradição entre Γ e Ф iii ou há contradição entre Γ e Ψ iv ou há contradição entre Ф e Ψ i se Γ é insatisfatível então Γ Ψ por vacuidade logo Γ U Ф Ψ ii se Γ U Ф é insatisfatível Γ U Ф Ψ por vacuidade iii se Γ U Ψ é insatisfatível Γ Ψ logo Γ U Ф Ψ iv se Ф Ψ é insatisfatível Ф Ψ logo Γ U Ф Ψ