UNIP GAB P1 ADS Lógica 2019

Prévia do material em texto

1
1 
 
 
GABARITO - P1 
 
O Cálculo Proposicional é a parte da Lógica Matemática que estuda a validade de argumentos 
apresentados em uma linguagem própria, a linguagem proposicional. Nessa linguagem é 
possível distinguir dois aspectos: o sintático e o semântico. O sintático estabelece símbolos, 
regras de formação e regras de dedução de validade. O aspecto semântico consiste na 
valoração das fórmulas com atribuição da propriedade de verdadeiro ou falso. 
O cálculo proposicional trabalha com tabelas-verdade tautologias e métodos dedutivos que 
visam estabelecer a validade de argumentos. Constitui-se um sistema formal no qual se pode 
operar com grande precisão e rigor algumas transformações e obter resultados bem definidos e 
de ampla aplicação em diversas áreas da Ciência. 
 
QUESTÃO 01 - (1,0 pt) O processo de formalização consiste em converter um conjunto de 
proposições interligadas em uma estrutura composta de letras proposicionais, conectivos 
lógicos e símbolos de pontuação. Os símbolos utilizados nessa operação são: 
• letras proposicionais: A, B,....P, Q, R etc, ou P1, P2,.... ou a, b, c,...ou p1, p2,p3...; 
• conectivos proposicionais: ~, ∧, ∨, →, ↔ 
• parênteses: ( ). 
 
Traduzir para a linguagem formal a seguinte sentença: 
 
Se a soma dos ângulos internos de um triângulo é igual a 360° e a soma de ângulos internos de 
um polígono convexo é definida por (𝑛 − 2).80, então a soma dos ângulos internos de um 
triângulo não é igual a 360°. 
Tradução: 
𝑝: a soma dos ângulos internos de um triângulo é igual a 360° 
𝑞: a soma de ângulos internos de um polígono convexo é definida por (𝑛 − 2).80 
Simbolicamente: (𝑝 ∧ 𝑞) → ~𝑝 
 
QUESTÃO 02 - (1,0 pt – 0,25pt cada item) Sejam as especificações de um sistema: 
𝑣: o usuário digita uma senha válida. 
𝑎: o acesso é concedido ao usuário. 
𝑐: o usuário entrou em contato com o administrador da rede. 
Traduza para a linguagem corrente as seguintes proposições: 
a) 𝑣 ∧ ~𝑎 
O usuário digita uma senha válida, mas o acesso foi negado. 
b) 𝑐 ∧ ~𝑣 
o usuário entrou em contato com o administrador da rede, mas não digitou uma senha 
válida. 
c) (𝑐 ∨ 𝑣) → 𝑎 
O acesso é concedido se que o usuário entrar em contato com o administrador da rede 
ou digitar uma senha válida. 
d) (~𝑣 ∨ ~𝑐) → ~𝑎 
O acesso é negado se o usuário não tiver digitado uma senha válida ou não tiver 
contatado o administrador da rede. 
ANÁLISE E DESENVOLVIMENTO DE SISTEMAS 
Lógica – 1º sem/2019 – Prof. Márcio 
 2
1 
 
QUESTÃO 03 - (1,0 pt) Na lógica proposicional, definem-se regras para determinar o valor-
verdade (verdadeiro ou falso) de sentenças em relação a um modelo particular. Essas regras 
permitem representar raciocínios lógicos comuns das linguagens naturais. 
Nesse contexto, considere a sentença e as proposições lógicas a seguir. 
“Um veículo que é elétrico (𝐸) pode ser um robô (𝑅) se for autônomo (𝐴), caso contrário não é 
um robô (R)” 
𝑃1 = (𝐸 ∧ 𝑅) ↔ 𝐴; 
𝑃2 = 𝐸 → (𝑅 ↔ 𝐴); 
𝑃3 = 𝐸 → ((𝐴 → 𝑅) ∨ ~𝑅) 
A sentença pode ser representada pela(s) expressão(ões) lógica(s) 
A. P2, apenas 
B. P3, apenas 
C. P1 e P2, apenas 
D. P1 e P3, apenas 
E. P1, P2 e P3 
 
QUESTÃO 4 – (1,0 pt – 0,2 cada linha) Encontre o valor Verdadeiro ou Falso para as 
expressões lógicas. 
Considere os seguintes valores para os endereços de memória: A:= 0, B:= 2, C:= 3, D:= 1. 
 A=D F cos(A)=D V A=C F 
A<B V (A=D) E (B < A) F (X<=Y) OU (X>Y) V 
B>A V (A<C) OU (A=B) V (X <>X) E (X=X) F 
A>C F (A=D)OU (A=C) OU (A=B) F (A+B)<(C+D) V 
(C < A) OU (C=A) F (D>B) E (X< A) F (A+B+C+D) > B×C F 
Atenção: É necessário acertar toda uma linha para receber os pontos da linha. 
Semântica: define o significado das sentenças 
O valor-verdade de uma proposição composta é obtido de forma única a partir dos valores-
verdade atribuídos às proposições simples que a compõem. A atribuição de um valor-verdade 
para uma proposição simples depende do seu contexto e faz parte do estudo semântico. 
Para determinar o valor-verdade (V) ou (F) de uma proposição composta, usa-se um 
instrumento denominado tabela-verdade, na qual figuram todas as possíveis combinações dos 
valores verdade das proposições simples. E o valor verdade de uma proposição composta 
depende unicamente do valor lógico de suas proposições simples. Uma proposição composta 
contendo n proposições simples admite 2n interpretações distintas, e a tabela-verdade avalia 
cada interpretação possível. 
Em lógica proposicional podemos descrever as proposições como: 
Válida (tautológica): é verdadeira em toda interpretação. 
Satisfatível (contingente): é verdadeira em alguma interpretação 
Insatisfatível (contraditória): é verdadeira em nenhuma interpretação. 
 
 
 
 
 
 3
1 
QUESTÃO 05 - (1,0 pt) Em uma seleção para uma vaga de programador, o setor de recursos 
humanos de uma empresa criou sentenças essenciais para a escolha do candidato, 
representadas pelas variáveis proposicionais 𝑝, 𝑞 e 𝑟: 
𝑝: o candidato tem experiência com a linguagem Python; 
𝑞: o candidato tem experiência com a linguagem Java; 
𝑟: o candidato é pouco experiente como programador. 
A partir das três sentenças criadas, foi gerada uma proposição composta S para a avaliação 
dos candidatos 
𝑆 = (𝑝 ∨ 𝑞) ∧ (𝑞 ∧ ~𝑟) 
Assinale a opção que representa corretamente a tabela-verdade do cálculo proposicional S. 
 
A. 
𝑝 𝑞 𝑟 (𝑝 ∨ 𝑞) (𝑞 ∧ ~𝑟) 𝑆 
V V V V V V 
V V F V V V 
V F V V F F 
V F F V V V 
F V V V V V 
F V F V F F 
F F V F F F 
F F F F V F 
 
 
B. 
𝑝 𝑞 𝑟 (𝑝 ∨ 𝑞) (𝑞 ∧ ~𝑟) 𝑆 
V V V V F V 
V V F V V V 
V F V V F V 
V F F V F V 
F V V V F V 
F V F V V V 
F F V F F F 
F F F F F F 
 
 
C. 
𝑝 𝑞 𝑟 (𝑝 ∨ 𝑞) (𝑞 ∧ ~𝑟) 𝑆 
V V V V V V 
V V F V F F 
V F V V F F 
V F F V F F 
F V V V V V 
F V F V F F 
F F V F F F 
F F F F F F 
 
D. 
𝑝 𝑞 𝑟 (𝑝 ∨ 𝑞) (𝑞 ∧ ~𝑟) 𝑆 
V V V V F F 
V V F V V V 
V F V V F F 
V F F V F F 
F V V V F F 
F V F V V V 
F F V F F F 
F F F F F F 
 
 
QUESTÃO 06 - (1,0 pt) A seguir, é apresentada a tabela-verdade para as proposições p, q e r 
diante da fórmula G, em que V representa uma proposição verdadeira e F uma proposição 
falsa. 
p q r G 
V V V V 
V V F F 
V F V F 
V F F F 
F V V V 
F V F V 
F F V V 
F F F V 
 4
1 
Considerando as informações contidas na tabela acima e a ordem de precedência dos 
operadores lógicos, a fórmula G possui a mesma tabela verdade da proposição 
A. p ∨ ~q ∧ r 
B. p ∨ q ∧ ~r 
C. ~p ∨ q ∧ r 
D. ~p ∨ ~q ∧ r 
E. ~p ∨ q ∧ ~r 
 
 
 
QUESTÃO 7 - (1,0 pt) Seja a tabela verdade do operador ⟷: 
p q p ⟷ q 
V V V 
V F F 
F V F 
F F V 
Pergunta: O operador ⟷ segue a lei da associatividade com o operador ∧, isto é: 
(p ⟷ q) ∧ r ⟺ p ⟷ (q ∧ r) ? 
Espaço para construir a tabela 
 
p q r (p ⟷ q) ∧ r p ⟷ (q ∧ r) 
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 ∧ 
 
 
QUESTÃO 08 - (1,0 pt – 0,5 pt cada item) As implicações e equivalências são demonstradas 
usando-se as tabelas-verdade. Essa abordagem é perfeitamente válida, porém, quando as 
sentenças lógicas tornam-se mais complexas, seu uso torna-se inviável. Nesta questão, as 
demonstrações devem ser realizadas por um método mais eficiente, denominado método 
dedutivo. 
? 
NÃO SÃO IDÊNTICAS 
 
p q r G A B C D E 
V V V V V V V F F 
V V F F V V F F V 
V F V F V V F V F 
V F F F V V F F F 
F V V V F F V V V 
F V F V F V V V V 
F F V V V F V V V 
FF F V F F V V V 
 
 5
1 
Demonstre, utilizando as equivalências notáveis, que as relações de implicação são válidas: 
a) Regra da simplificação: p  q  q 
Para provarmos uma relação de implicação temos que demonstrar que a condicional p  q 
→ q é tautológica, ou seja, que a condicional p  q → q  V . 
Desenvolvendo o lado esquerdo da equivalência, tem-se: 
Proposição Justificativa 
p  q → q  (aplicando-se a equiv. de reescrita da condicional) 
~ ( p  q )  q  (aplicando-se a Lei de Morgan) 
~p  ~q  q  (aplicando-se lei complementar, ¬q  q é uma tautologia) 
~p  V  (pela lei da identidade ¬p  V é um tautologia) 
V Portanto, está provado que p  q  q é uma tautologia 
 
b) Regra de Modus Ponens: (p → q)  p  q 
Deve-se demonstrar que a relação de implicação equivale a uma tautologia: 
(p → q)  p → q  V 
Proposição Justificativa 
(~p  q)  q → q  Condicional 
(q  ~p)  (q  q) → q  Distributiva 
(q  ~p)  q → q  Idempotente 
~ ((q  ~p)  q)  q  Condicional 
(~ (q  ~p)  ~q )  q  De Morgan 
((~q  p)  ~q)  q  De Morgan 
(~q  ~q)  (~q  p)  q  Distributiva 
~q  (~q  p)  q  Idempotente 
(~q  q)  (~q  p )  Associativa 
V  (~q  p )  Complementares 
V Identidade 
 
 
QUESTÃO 9 – (1,0 pt – 0,5 pt cada item) Utilizando equivalências notáveis, demonstre as 
seguintes tautologias 
a) (𝑝 → 𝑞) ∨ (𝑝 → 𝑟) ⟺ 𝑝 → (𝑞 ∨ 𝑟) 
Proposição Justificativa 
(𝑝 → 𝑞) ∨ (𝑝 → 𝑟) 
(~𝑝 ∨ 𝑞) ∨ (~𝑝 ∨ 𝑟) Condicional 
(𝑞 ∨ ~𝑝) ∨ (𝑟 ∨ ~𝑝) Comutativa 
𝑞 ∨ (~𝑝 ∨ 𝑟) ∨ ~𝑝 Associativa 
𝑞 ∨ (𝑟 ∨ ~𝑝) ∨ ~𝑝 Comutativa 
(𝑞 ∨ 𝑟) ∨ (~𝑝 ∨ ~𝑝) Associativa 
(𝑞 ∨ 𝑟) ∨ ~𝑝 Idempotência 
~𝑝 ∨ (𝑞 ∨ 𝑟) Comutativa 
𝑝 → (𝑞 ∨ 𝑟) Condicional 
 
b) (𝑝 ∧ 𝑞) ∨ ~𝑝 ⟺ ~𝑞 → ~𝑝 
Proposição Justificativa 
(𝑝 ∧ 𝑞) ∨ ~𝑝 
~𝑝 ∨ (𝑝 ∧ 𝑞) Comutativa 
(~𝑝 ∨ 𝑝) ∧ (~𝑝 ∨ 𝑞) Distributiva 
𝑉 ∧ (~𝑝 ∨ 𝑞) Identidade 
~𝑝 ∨ 𝑞 Comutativa 
𝑞 ∨ ~𝑝 Comutativa 
~(~𝑞 ∧ 𝑝) De Morgan 
~𝑞 → ~𝑝 Condicional 
 
Bastou mostrar a validade dos argumentos: 
 6
1 
no item a: (𝑝 → 𝑞) ∨ (𝑝 → 𝑟) → 𝑝 → (𝑞 ∨ 𝑟) e (~𝑞 → ~𝑝) → (𝑝 ∧ 𝑞) ∨ ~𝑝 neste argumento foi 
utilizado o mesmo processo de baixo para cima pois foram utilizadas somentes equivalências 
lógicas. 
no item b: (𝑝 ∧ 𝑞) ∨ ~𝑝 → ~𝑞 → ~𝑝 e 𝑝 → (𝑞 ∨ 𝑟) → (𝑝 → 𝑞) ∨ (𝑝 → 𝑟) neste argumento foi 
utilizado o mesmo processo de baixo para cima pois foram utilizadas somentes equivalências 
lógicas. 
QUESTÃO 10 – (1,0 pt) Reescreva o teste abaixo reduzindo as condições através das relações 
de equivalência 
 
SE ~(idade > 21  sexo="F")  ( ~(idade > 21)  sexo="F") ENTÃO 
 faça bloco de comandos A 
SENÃO 
 faça bloco de comandos B 
Fazendo p: idade > 21 e q: sexo = "F": 
~(p  q)  (~p  q)  
(~p  ~q)  (~p  q)  (De Morgan) 
~p  (~q  q)  (Distributiva) 
~p  V  (Complem.) 
~p (Identidade) 
 
Se idade  21 
 faça bloco A 
Senão 
 faça bloco B 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 7
1 
 
Tabela de Equivalências Notáveis 
Equivalências Denominação 
p  V ⇔ p 
p  F ⇔ p 
Leis de Identidade 
p  V ⇔V 
p  F ⇔ F 
Leis de Dominância 
 p  p ⇔ V 
 p  p ⇔ F 
Lei Complementar 
p  p ⇔ p 
p  p ⇔ p 
Leis de Idempotência 
 ( p) ⇔ p Lei da dupla negação 
p  q ⇔ q  p 
p  q ⇔ q  p 
Leis Comutativas 
(p  q)  r ⇔ p  (q  r) 
(p  q)  r ⇔ p  (q  r) 
Leis Associativas 
p  (q  r) ⇔ (p  q)  (p  r) 
p  (q  r) ⇔ (p  q)  (p  r) 
Leis Distributivas 
p  (pq) ⇔ p 
p  (pq) ⇔ p 
Lei da absorção 
p → q ⇔ p  q Lei da Condicional 
(p → q) ⇔ p  q Negação da Condicional 
p ↔ q ⇔ (p → q)  (q → p) Lei da Bicondicional 
(p ↔ q) ⇔ (p  ~ q)  (q  p) Negação da Bicondicional 
 (p  q) ⇔  p   q 
 (p  q) ⇔  p   q 
Leis de De Morgan