Baixe o app para aproveitar ainda mais
Prévia do material em texto
2ª LISTA DE EXERCÍCIOS 1) Verifique, usando a definição de consequência lógica, se pode ser escrito: Definição de consequência lógica: “Uma fórmula α é consequência lógica de um conjunto de fórmulas Τ se toda interpretação que satisfaz todas as fórmulas de Τ também satisfaz α. a) ((¬p→q ), (r∧¬q) )╞ p→r p q r ¬p ¬q ¬p→q r∧¬q p→r v v v f f v f v v v f f f v f f v f v f v v v v v f f f v v f f f v v v f v f v f v f v f v f v f f v v v f v v f f f v v f f v Segundo a definição p→r é consequência lógica de ((¬p→q ), (r∧¬q) ) b) ((¬p→q )∨(r∧¬q ) )╞ p→¬r p q r ¬p ¬q ¬r ¬p→q r∧¬q (¬p→q )∨(r∧¬q) p→¬r v v v f f f v f v f v v f f f v v f v v v f v f v f v v v f v f f f v v v f v v f v v v f f v f v v f v f v f v v f v v f f v v v f f v v v f f f v v v f f f v Segundo a definição p→¬r não é consequência lógica de ((¬p→q )∨(r∧¬q )) , pois as interpretações I [1] e I [3] não satisfazem. c) (( p→q) ,(r∧¬q ) )╞ p→r p q r ¬q p→q r∧¬q p→r v v v f v f v v v f f v f f v f v v f v v v f f v f f f f v v f v f v f v f f v f v f f v v v v v f f f v v f v Segundo a definição p→r é consequência lógica de ((¬p→q ), (r∧¬q)) . d) (¬( p∨q ))↔(¬r→¬q) ,¬q╞ (( p∧¬q)∨r ) p q r ¬q ¬r p∨q ¬(p∨q ) ¬r→¬q (¬(p∨q ))↔(¬r→¬q) p∧¬q ( p∧¬q)∨r v v v f f v f v f f v v v f f v v f f v f f v f v v f v f v f v v v f f v v v f v f v v f v v f f v f v f f v f v f f v v f f v f f f f v v f f v v v f v f f f v v f v v v f f Segundo a definição ( p∧¬q)∨r não é consequência lógica de (¬( p∨q ))↔(¬r→¬q) ,¬q , pois a interpretação I [8 ] não satisfaz. e) ( p∧q∧r)→(¬r↔¬q) ,¬r╞ p→r p q r ¬q ¬r p∧q∧r ¬r↔¬q ( p∧q∧r)→(¬r↔¬q) p→r v v v f f v v v v v v f f v f f v f v f v v f f f v v v f f v v f v v f f v v f f f v v v f v f f v f f v v f f v v f f f v v f f f v v f v v v Segundo a definição p→r não é consequência lógica de ( p∧q∧r)→(¬r↔¬q) ,¬r , pois as interpretações I [2] e I [4] não satisfazem. f) p→ (q∨r ), p╞ p∧q p q r q∨r p→ (q∨r ) p∧q v v v v v v v v f v v v v f v v v f v f f f f f f v v v v f f v f v v f f f v v v f f f f f v f Segundo a definição p∧q não é consequência lógica de p→ (q∨r ) e p , pois as interpretações I [2] e I [4] não satisfazem. g) ¬p→¬¬q ,¬¬¬p╞ q p q ¬p ¬¬p ¬¬¬p ¬q ¬¬q ¬p→¬¬q v v f v f f v v v f f v f v f v f v v f v f v v f f v f v v f f Segundo a definição q é consequência lógica de ¬p→¬¬q e ¬¬¬p . h) ( p∧q)→(r∧s),¬¬p ,q╞ s p q r s ¬p ¬¬p p∧q r∧s ( p∧q)→(r∧s) v v v v f v v v v v v v f f v v f f v v f v f v v f f v v f f f v v f f v f v v f v f v v v f v f f v f f v v f f v f v f f v v f f f f v f f v f v v v v f f v v f v v f v f f f v f v f v v f f f v f v f f v f f f v f f v v v f f v v f f v f v f f f v f f f v v f f f v f f f f v f f f v Segundo a definição s é consequência lógica de ( p∧q)→(r∧s) , ¬¬p e q . i) p╞ ( p∨q)∧( p∨r ) p q r p∨q p∨r ( p∨q)∧( p∨r ) v v v v v v v v f v v v v f v v v v v f f v v v f v v v v v f v f v f f f f v f v f f f f f f f Segundo a definição ( p∨q)∧( p∨r ) é consequência lógica de p . j) p ,¬¬( p→q)╞q∨¬q p q ¬q p→q ¬(p→q) ¬¬( p→q) q∨¬q v v f v f v v v f v f v f v f v f v f v v f f v v f v v Segundo a definição q∨¬q é consequência lógica de p e ¬¬( p→q) . k) p↔(q∨r ) , q╞ p p q r q∨r p↔(q∨r ) v v v v v v v f v v v f v v v v f f f f f v v v f f v f v f f f v v f f f f f v Segundo a definição p é consequência lógica de p↔(q∨r ) e q . l) p ,( p∧q)→¬r ,¬r→¬s╞ q→¬s p q r s ¬r ¬s p∧q ( p∧q)→¬r ¬r→¬s q→¬s v v v v f f v f v f v v v f f v v f v v v v f v v f v v f f v v f f v v v v v v v f v v f f f v v v v f v f f v f v v v v f f v v f f v f v v f f f v v f v v v f v v v f f f v v f f v v f f v f v v v f v f v v f f v f f f v f f v v f v v v f f v v f f f v v v f f v f f v f v v v f f f v v f f v f v f f f f v v f v v v Segundo a definição q→¬s é consequência lógica de p , ( p∧q)→¬r e ¬r→¬s . m) ¬p→ p╞ p p ¬p ¬p→ p v f v f v f Segundo a definição p é consequência lógica de ¬p→ p . n) p→¬¬q╞¬q→¬p p q ¬p ¬q ¬¬q p→¬¬q ¬q→¬p v v f f v v v v f f v f f f f v v f v v v f f v v f v v Segundo a definição ¬q→¬p é consequência lógica de p→¬¬q . o) ¬p↔(¬q∨¬r ) , r∧p╞ p p q r ¬p ¬q ¬r ¬q∨¬r ¬p↔(¬q∨¬r ) r∧p v v v f f f f v v v v f f f v v f f v f v f v f v f v v f f f v v v f f f v v v f f f f f f v f v f v v v f f f v v v f v v f f f f v v v v v f Segundo a definição p é consequência lógica de ¬p↔(¬q∨¬r ) e r∧p . 2) Repita o exercício (1), mas agora usando o resultado estabelecido no Teorema 1.1. Definição: Dadas as fórmulas β1 , β2 , β3 ..., βn e uma fórmula α , diz- se que α é consequência lógica de β1 , β2 , β3 ..., βn se, e somente se, a fórmula β1∧β2∧β3∧...∧βn→α a for uma tautologia. a) ((¬p→q ), (r∧¬q) )╞ p→r p q r ¬p ¬q ¬p→q r∧¬q p→r (¬p→q)∧(r∧¬q) ((¬p→q)∧(r∧¬q))→( p→r ) v v v f f v f v f v v v f f f v f f f v v f v f v v v v v v v f f f v v f f f v f v v v f v f v f v f v f v f v f v f v f f v v v f v v f v f f f v v f f v f v b) ((¬p→q )∨(r∧¬q ) )╞ p→¬r p q r ¬p ¬q ¬r ¬p→q r∧¬q (¬p→q )∨(r∧¬q) p→¬r ((¬p→q)∨(r∧¬q))→( p→¬r ) v v v f f f v f v f f v v f f f v v f v v v v f v f v f v v v f f v f f f v v v f v v v f v v v f f v f v v v f v f v f v v f v v v f f v v v f f v v v v f f f v v v f f f v v c) (( p→q) ,(r∧¬q ) )╞ p→r p q r ¬q p→q r∧¬q p→r ( p→q)∧(r∧¬q ) (( p→q)∧(r∧¬q))→( p→r) v v v f v f v f v v v f f v f f f v v f v v f v v f v v f f v f f f f v f v v f v f v f v f v f f v f v f v f f v v v v v v v f f f v v f v f v d) (¬( p∨q ))↔(¬r→¬q) ,¬q╞ (( p∧¬q)∨r ) p q r ¬q ¬r p∨q ¬(p∨q ) ¬r→¬q (¬(p∨q ))↔(¬r→¬q) p∧¬q ( p∧¬q)∨r v v v f f v f v f f v v v f f v v f f v f f v f v v f v f v f v v v f f v v v f v f v v f v v f f v f v f f v f v f f v v f f v f f f f v v f f v v v f v f f f v v f v v v f f Cont… ((¬( p∨q))↔(¬r→¬q))∧¬q (((¬( p∨q))↔(¬r→¬q))∧¬q)→(( p∧¬q )∨r ) f v f v f v f v f v f v v v v f e) ( p∧q∧r)→(¬r↔¬q) ,¬r╞ p→r p q r ¬q ¬r p∧q∧r ¬r↔¬q ( p∧q∧r)→(¬r↔¬q) p→r v v v f f v v v v v v f f v f f v f v f v v f f f v v v f f v v f v v f f v v f f f v v v f v f f v f f v v f f v v f f f v v f f f v v f v v v (( p∧q∧r )→(¬r↔¬q))∧¬r ((( p∧q∧r)→(¬r↔¬q))∧¬r )→(p→r ) f v v f f v v f f v v v f v v v f) p→ (q∨r ), p╞ p∧q p q r q∨r p→ (q∨r ) p∧q ( p→(q∨r ))∧p (( p→(q∨r ))∧p)→( p∧q) v v v v v v v v v v f v v v v v v f v v v f v f v f f f f f f v f v v v v f f v f v f v v f f v f f v v v f f v f f f f v f f v g) ¬p→¬¬q ,¬¬¬p╞ q p q ¬p ¬¬p ¬¬¬p ¬q ¬¬q ¬p→¬¬q (¬p→¬¬q)∧(¬¬¬p) ((¬p→¬¬q)∧(¬¬¬p))→(q) v v f v f f v v f v v f f v f v f v f v f v v f v f v v v v f f v f v v f f f v h) ( p∧q)→(r∧s),¬¬p ,q╞ s p q r s ¬p ¬¬p p∧q r∧s v v v v f v v v v v v f f v v f v v f v f v v f v v f f f v v f v f v v f v f v v f v f f v f f v f f v f v f f v f f f f v f f f v v v v f f v f v v f v f f f f v f v v f f f f v f f v f f f f f v v v f f v f f v f v f f f f f f v v f f f f f f f v f f f Cont... (( p∧q)→(r∧s))∧(¬¬p)∧q ((( p∧q)→(r∧s))∧(¬¬ p)∧q)→s v v f v f v f v f v f v f v f v f v f v f v f v f v f v f v f v i) p╞ ( p∨q)∧( p∨r ) p q r p∨q p∨r ( p∨q)∧( p∨r ) p→ (( p∨q)∧( p∨r )) v v v v v v v v v f v v v v v f v v v v v v f f v v v v f v v v v v v f v f v f f v f f v f v f v f f f f f f v j) p ,¬¬( p→q)╞q∨¬q p q ¬q p→q ¬(p→q) ¬¬( p→q) q∨¬q p∧(¬¬( p→q )) ( p ,¬¬( p→q))→(q∨¬q)v v f v f v v v v v f v f v f v f v f v f v f v v f v f f v v f v v f v k) p↔(q∨r ) , q╞ p p q r q∨r p↔(q∨r ) ( p↔(q∨r))∧q (( p↔(q∨r ))∧q)→p v v v v v v v v v f v v v v v f v v v f v v f f f f f v f v v v f f v f v f v f f v f f v v f f v f f f f v f v l) p ,( p∧q)→¬r ,¬r→¬s╞ q→¬s p q r s ¬r ¬s p∧q ( p∧q)→¬r ¬r→¬s q→¬s v v v v f f v f v f v v v f f v v f v v v v f v v f v v f f v v f f v v v v v v v f v v f f f v v v v f v f f v f v v v v f f v v f f v f v v f f f v v f v v v f v v v f f f v v f f v v f f v f v v v f v f v v f f v f f f v f f v v f v v v f f v v f f f v v v f f v f f v f v v v f f f v v f f v f v f f f f v v f v v v Cont... ( p∧(( p∧q)→¬r)∧(¬r→¬s)) ( p∧(( p∧q)→¬r)∧(¬r→¬s))→(q→¬s) f v f v f v v v v v v v f v v v f v f v f v f v f v f v f v f v m) ¬p→ p╞ p p ¬p ¬p→p (¬p→p)→p v f v v f v f v n) p→¬¬q╞¬q→¬p p q ¬p ¬q ¬¬q p→¬¬q ¬q→¬p ( p→¬¬q)→(¬q→¬p) v v f f v v v v v f f v f f f v f v v f v v v v f f v v f v v v o) ¬p↔(¬q∨¬r ) , r∧p╞ p p q r ¬p ¬q ¬r ¬q∨¬r ¬p↔(¬q∨¬r ) r∧p v v v f f f f v v v v f f f v v f f v f v f v f v f v v f f f v v v f f f v v v f f f f f f v f v f v v v f f f v v v f v v f f f f v v v v v f Cont... (¬p↔(¬q∨¬r ))∧(r∧p) ((¬p↔(¬q∨¬r ))∧(r∧p))→ p v v f v f v f v f v f v f v f v 3) Considere que: Se o universo é finito, então a vida é curta. Se a vida vale a pena, então a vida é complexa. Se a vida é curta ou complexa, então a vida tem sentido. A vida não tem sentido. p : o universo é finito q : a vida é curta r : a vida vale a pena s : a vida é complexa t : a vida tem sentido Verifique, usando regras de inferência e equivalências lógicas: a) Se o universo é finito e a vida vale a pena, então a vida tem sentido. ( p∧r )→t Tem-se: C1 p→q premissa C2 r→s premissa C3 (q∨s)→t premissa C4 ¬t premissa Deduz-se: C5 p∧r hipótese condicional C6 p (C5 + simplificação) C7 q (C1 + C6 + modus ponens) C8 q∨s (C7 + adição) C9 t (C3 + C8 + modus ponens) C10 ( p∧r )→t (C5 - C9 + introdução da condicional) b) A vida não é curta. ¬q Tem-se: C1 p→q premissa C2 r→s premissa C3 (q∨s)→t premissa C4 ¬t premissa Deduz-se: C5 ¬(q∨s ) (C3 + C4 + modus tollens) C6 ¬q∧¬s (C5 + De Morgan) C7 ¬s (C6 + Simplificação) C8 ¬q (C6 + Simplificação) c) A vida não é complexa ou o universo não é finito. ¬s∨¬p Tem-se: C1 p→q premissa C2 r→s premissa C3 (q∨s)→t premissa C4 ¬t premissa Deduz-se: C5 ¬(q∨s ) (C3 + C4 + modus tollens) C6 ¬q∧¬s (C5 + De Morgan) C7 ¬s (C6 + Simplificação) C8 ¬s∨¬p (C7 + adição) d) A vida vale a pena se e somente se a vida tem sentido. r↔ t Tem-se: C1 p→q premissa C2 r→s premissa C3 (q∨s)→t premissa C4 ¬t premissa Deduz-se: C5 ¬(r↔ t) hipótese absurdo C6 ¬(q∨s ) (C3 + C4 + modus tollens) C7 (q∨s)→t (C6 + De Morgan) C8 ¬s (C7 + simplificação) C9 ¬((r→t)∧(t→r )) (C5 + equivalência da bicondicional) C10 ¬((¬r∨t)∧(¬t∨r)) (C9 + equivalência da condicional) C11 ¬(¬r∨t)∨¬(¬t∨r ) (C10 + De Morgan) C12 (¬¬r∧¬t )∨(¬¬t∧¬r ) (C11 + De Morgan) C13 (r∧¬t )∨(t∧¬r ) (C12 + dupla negação) C14 ((r∧¬t )∨t)∧((r∧¬t )∨¬r ) (C13 + distributiva) C15 (r∨t)∧(¬t∨t)∧(r∨¬r )∧(¬t∨¬r ) (C14 + distributiva) C16 r∨t (C15 + simplificação) C17 r (C4 + C16 + silogismo disjuntivo) C18 s (C2 + C17 + modus ponens) C19 s∧¬s (C8 + C18 + conjunção) C20 r↔ t (C5 + C19 + redução ao absurdo) 4) Dado que: Eu não como muito ou eu engordo. Se chove, então a temperatura cai. Se eu engordo ou a temperatura cai, então assisto TV. Não assisto TV. p : eu como muito q : eu engordo r : chove s : a temperatura cai t : assisto TV Verifique, usando regras de inferência, consequências e equivalências lógicas, se as assertivas a seguir são válidas: a) Se eu não como muito e chove, então assisto TV. (¬p∧r)→t Tem-se: C1 ¬p∨q premissa C2 r→s premissa C3 (q∨s)→t premissa C4 ¬t premissa Deduz-se: C5 ¬p∧r hipótese condicional C6 r (C5 + simplificação) C7 s (C2 + C6 + modus ponens) C8 ¬(q∨s ) (C3 + C4 + modus tollens) C9 ¬q∧¬s (C8 + De Morgan) C10 ¬s (C9 + simplificação) C11 s∧¬s (C7 + C10 + conjunção) R: A sequência C1, C2, C3, C4, C5, C6, C7, C8, C9, C10, C11 é uma prova da conclusão (¬p∧r)→t e o argumento (¬p∨q) ,(r→s) ,((q∨s)→t ) ,(¬t) ∣− ((¬p∧r )→t) é inválido. b) Se a temperatura cai ou eu engordo, então eu não como muito. (s∨q)→¬p Tem-se: C1 ¬p∨q premissa C2 r→s premissa C3 (q∨s)→t premissa C4 ¬t premissa Deduz-se: C5 s∨q hipótese condicional C6 ¬(q∨s ) (C3 + C4 + modus tollens) C7 ¬q∧¬s (C6 + De Morgan) C8 ¬q (C7 + simplificação) C9 ¬p (C1 + C8 + silogismo disjuntivo) C10 (s∨q)→¬p (C5 - C9 + introdução da condicional) R: A sequência C1, C2, C3, C4, C5, C6, C7, C8, C9 é uma prova da conclusão (s∨q)→¬p e o argumento (¬p∨q) ,(r→s) ,((q∨s)→t) ,(¬t) ∣− ((s∨q)→¬p) é válido. 5) Identifique os átomos, construa o argumento e verifique a validade para as situações: a) Se Deus existe, então a vida tem significado. Deus existe. Portanto, A vida tem significado. p : Deus existe q : a vida tem significado Argumento: p→q , p ∣− q Tem-se: C1 p→q premissa C2 p premissa Deduz-se: C3 ¬p∨q (C1 + De Morgan) C4 q (C2 + C3 + silogismo disjuntivo) R: A sequência C1, C2, C3, C4 é uma prova da conclusão q e o argumento p→q , p ∣− q é válido. b) Deus não existe. Se Deus existisse, a vida teria significado. Portanto, a vida não tem significado. p : Deus existe q : a vida tem significado Argumento: ¬p ,¬p→¬q ∣− ¬q Tem-se: C1 ¬p premissa C2 ¬p→¬q premissa Deduz-se: C3 ¬¬p∨¬q (C2 + De Morgan) C4 p∨¬q (C3 + dupla negação) C5 ¬q (C1 + C4 + silogismo disjuntivo) R: A sequência C1, C2, C3, C4, C5 é uma prova da conclusão ¬q e o argumento ¬p ,¬p→¬q ∣− ¬q é válido. c) Como hoje não é quinta-feira, deve ser sexta-feira. Logo, hoje é quinta-feira ou sexta-feira. p : hoje é quinta-feira q : hoje é sexta-feira Argumento: ¬p ,q ∣− p∨q Tem-se: C1 ¬p premissa C2 q premissa Deduz-se: C3 p∨q (C2 + adição) R: A sequência C1, C2, C3 é uma prova da conclusão p∨q e o argumento ¬p ,q ∣− p∨q é válido. d) Se hoje for quinta-feira, então amanhã será sexta-feira. Se amanhã for sexta-feira, então depois de amanhã será sábado. Consequentemente, se hoje for quinta-feira, então depois de amanhã será sábado. p : hoje é quinta-feira q : amanhã será sexta-feira r : depois de amanhã será sábado Argumento: p→q ,q→r ∣− p→r Tem-se: C1 p→q premissa C2 q→r premissa Deduz-se: C3 p hipótese condicional C4 q (C1 + C3 + modus ponens) C5 r (C2 + C4 + modus ponens) C6 p→r (C3 + C5 + introdução da condicional) R: A sequência C1, C2, C3, C4, C5, C6 é uma prova da conclusão p→r e o argumento p→q ,q→r ∣− p→r é válido. e) Hoje é um fim de semana se e somente se hoje for sábado ou domingo. Portanto, hoje é um fim de semana, desde que hoje seja sábado. p : hoje é fim de semana q : hoje é sábado r : hoje é domingo Argumento: p↔(q∨r ) ∣− p→q Tem-se: C1 p↔(q∨r ) premissa Deduz-se: C2 q hipótese condicional C3 ( p→(q∨r ))∧(q∨r )→ p (C1 + equivalência da bicondicional) C4 (q∨r )→ p (C3 + simplificação) C5 q∨r (C2 + adição) C6 p (C4 + C5 + modus ponens) C7 p→q (C6 - C2 + introdução da condicional) R: A sequência C1, C2, C3, C4, C5, C6, C7 é uma prova da conclusão p→q e o argumento p↔(q∨r ) ∣− p→q é válido. f) Hoje é um fim de semana se e somente se hoje for sábado ou domingo. Hoje não é sábado. Hoje não é domingo. Portanto, hoje não é um fim de semana. p : hoje é fim de semana q : hoje é sábado r : hoje é domingo Argumento: p↔(q∨r ) ,¬q ,¬r ∣− ¬ p Tem-se: C1 p↔(q∨r) premissa C2 ¬q premissa C3 ¬r premissa Deduz-se: C4 ¬p∨q (C2 + C3 + conjunção) C5 ¬(q∨r ) (C4 + De Morgan) C6 ( p→(q∨r ))∧(q∨r )→ p (C1 + equivalência da bicondicional) C7 p→ (q∨r ) (C6 + simplificação) C8 ¬p (C7 + modus tollens) R: A sequência C1, C2, C3, C4, C5, C6, C7, C8 é uma prova da conclusão ¬p e o argumento p↔(q∨r ) ,¬q ,¬r ∣− ¬ p é válido. g) Ela não está em casa ou não está atendendo ao telefone. Mas se ela não está em casa, então ela foi sequestrada. Se ela não está atendendo ao telefone, ela está correndo algum outro perigo. Portanto, ou ela foi sequestrada ou ela está correndo um outro perigo. p : ela está em casa q : ela está atendendo o telefone r : ela foi sequestrada s : ela está correndo perigo Argumento: ¬p∨¬q ,¬p→r ,¬q→s ∣− r∨s Tem-se: C1 ¬p∨¬q premissa C2 ¬p→r premissa C3 ¬q→ s premissa Deduz-se: C4 ¬(r∨s) hipótese absurdo C5 ¬r∧¬s (C4 + De Morgan) C6 p→¬q (C1 + equivalência da condicional) C7 ¬r (C5 + simplificação) C8 ¬s (C5 + simplificação) C9 p (C2 + C3 + modus tollens) C10 ¬q (C6 + C9 + modus ponens) C11 s (C3 + C10 + modus ponens) C12 ¬s∧s (C8 + C11 + conjunção) C13 r∨s (C4 + C12 + redução ao absurdo) R: A sequência C1 à C13 é uma prova da conclusão r∨s e o argumento ¬p∨¬q ,¬p→r ,¬q→s ∣− r∨s é válido. 6) Prove, usando as regras de inferência e o princípio da substituição, que os argumentos a seguir são válidos. a) α ∣− β→α Tem-se: C1 α premissa Deduz-se: C2 β hipótese condicional C3 β→α (C2 + C3 + introdução da condicional) b) ¬α→ (β→δ) ,¬α ,β ∣− δ Tem-se: C1 ¬α→ (β→δ) premissa C2 ¬α premissa C3 β premissa Deduz-se: C4 β→δ (C1 + C2 + modus ponens) C5 δ (C3 + C4 + modus ponens) c) ¬α→¬¬β ,¬¬¬α ∣− β Tem-se: C1 ¬α→¬¬β premissa C2 ¬¬¬α premissa Deduz-se: C3 ¬α (C2 + dupla negação) C4 ¬¬β (C1 + C3 + modus ponens) C4 β (C4 + dupla negação) d) α ∣− α∨α Tem-se: C1 α premissa Deduz-se: C2 α∨α (C1 + adição) e) α ∣− (α∨β)∧(α∨δ) Tem-se: C1 α premissa Deduz-se: C2 α∨β (C1 + adição) C3 α∨δ (C1 + adição) C4 (α∨β)∧(α∨δ) (C2 + C3 + conjunção) f) α→β ,(α→β)→(β→α) ∣− (α↔β) Tem-se: C1 α→β premissa C2 (α→β)→(β→α) premissa Deduz-se: C3 β→α (C1 + C2 + modus ponens) C4 (α→β)∧(β→α) (C1 + C3 + conjunção) α↔β C4 + equivalência da bicondicional) 7) Encontre uma fórmula equivalente à fórmula ¬(p∧q )∨r , em que só ocorra →. ¬(p∧q )∨r (¬p∨¬q)∨r De Morgan ( p→¬q)∨r Equivalência da condicional ¬(p→¬q)→r Equivalência da condicional p q r ¬q p∧q ¬(p∧q ) ¬(p∧q )∨r p→¬q ¬(p→¬q) ¬(p→¬q)→r v v v f v f v f v v v v f f v f f f v f v f v v f v v v f v v f f v f v v v f v f v v f f v v v f v f v f f f v v v f v f f v v f v v v f v f f f v f v v v f v 8) Verifique, justificando quais dos enunciados a seguir são verdadeiros. a) ¬(p∧q )∨q é uma contradição. p q p∧q ¬(p∧q ) ¬(p∧q )∨q v v v f v v f f v v f v f v v f f f v v R: ¬(p∧q )∨q não é uma contradição, pois pela tabela verdade é possível ver que todas as interpretações I são iguais a v , sendo assim ¬(p∧q )∨q é uma tautologia. b) ( p↔q∧¬p)↔¬q é uma contradição. p q ¬p ¬q q∧¬p p↔q∧¬p ( p↔q∧¬p)↔¬q v v f f f f v v f f v f f f f v v f v f v f f v v f v v R: ¬(p∧q )∨q não é uma contradição, pois pela tabela verdade é possível ver que as interpretações I1, I3 e I4 são iguais a v , sendo assim ( p↔q∧¬p)↔¬q é contigente, satisfatível e inválida. c) Se p for avaliado f então q≡¬ p∨q . p q ¬p ¬p∨q v v f v v f f f f v v v f f v v R: q não é equivalente a ¬p∨q , pois pela tabela verdade é possível ver que a interpretação I4 tem valor igual a f em q e valor igual a v em ¬p∨q . d) p∧p é insatisfatível. p p∧p v v f f R: p∧p não é insatisfatível, pois pela tabela verdade é possível ver que a interpretação I1 tem valor igual a v . e) p→ p é satisfatível. p p→ p v v f v R: p→ p é satisfatível, pois pela tabela verdade é possível ver que a interpretação I1 e I2 tem valor igual a v . f) p→ p é válida. p p→ p v v f v R: p→ p é válida, pois pela tabela verdade é possível ver que as interpretações I1 e I2 tem valor igual a v . g) p∨¬p é válida. p ¬p p∨¬p v f v f v v R: p∨¬p é válida, pois pela tabela verdade é possível ver que as interpretações I1 e I2 tem valor igual a v . 9) Usando tanto o método da tabela-verdade quanto o de manipulação algébrica de fórmulas via equivalência lógica, determine a FNC equivalente a: a) p→¬q Manipulação Algébrica p→¬q Equivalência da implicação ¬p∨¬q FNC Tabela-verdade p q ¬q p→¬q v v f f v f v v f v f v f f v v Focalizando as interpretações cujos valores-verdade de α são f , segundo o Procedimento, FNC( α ): ¬p∨¬q b) ¬(p∧q ) Manipulação Algébrica ¬(p∧q ) De Morgan ¬p∨¬q FNC Tabela-verdade p q p∧q ¬(p∧q ) v v v f v f f v f v f v f f f v Focalizando as interpretações cujos valores-verdade de α são f , segundo o Procedimento, FNC( α ): ¬p∨¬q c) ( p∧q)∨q Manipulação Algébrica ( p∧q)∨q Equivalência da implicação ( p∨q)∧(q∨q) Idempotentes ( p∨q)∧q FNC Tabela-verdade p q p∧q ( p∧q)∨q v v v v v f f f f v f v f f f f Focalizando as interpretações cujos valores-verdade de α são f , segundo o Procedimento, FNC( α ): (¬p∨q)∧( p∨q ) d) p∧¬(q∨r ) Manipulação Algébrica p∧¬(q∨r ) De Morgan p∧(¬q∧¬r) Associativa p∧¬q∧¬r FNC Tabela-verdade p q r q∨r ¬(q∨r ) p∧¬(q∨r ) v v v v f f v v f v f f v f v v f f v f f f v v f v v v f f f v f v f f f f v v f f f f f f v f Focalizando as interpretações cujos valores-verdade de α são f , segundo o Procedimento, FNC( α ): (¬p∨¬q∨¬r )∧(¬p∨¬q∨r )∧(¬p∨q∨¬r )∧( p∨¬q∨¬r)∧( p∨¬q∨r )∧(p∨q∨¬r)∧( p∨q∨r ) e) ¬(p∧(q∨r )) Manipulação Algébrica ¬(p∧(q∨r )) De Morgan ¬p∨¬(q∨r) De Morgan ¬p∨(¬q∧¬r ) Distributiva (¬p∨¬q)∧(¬p∨¬r ) FNC Tabela-verdade p q r q∨r p∧(q∨r ) ¬(p∧(q∨r )) v v v v v f v v f v v f v f v v v f v f f f f v f v v v f v f v f v f v f f v v f v f f f f f v Focalizando as interpretações cujos valores-verdade de α são f , segundo o Procedimento, FNC( α ): (¬p∨¬q∨¬r )∧(¬p∨¬q∨r )∧(¬p∨q∨¬r ) f) p∨(¬p∧q∧r) Manipulação Algébrica p∨(¬p∧q∧r) Distributiva ( p∨¬p)∧( p∨q)∧(p∨r ) p∧( p∨q )∧( p∨r ) FNC Tabela-verdade p q r ¬p ¬p∧q∧r p∨(¬p∧q∧r) v v v f f v v v f f f v v f v f f v v f f f f v f v v v v v f v f v f f f f v v f f f f f v f f Focalizando as interpretações cujos valores-verdade de α são f , segundo o Procedimento, FNC( α ): ( p∨¬q∨r )∧( p∨q∨¬r )∧( p∨q∨r) g) ¬(p→q)∨( p∨q) Manipulação Algébrica ¬(p→q)∨( p∨q) Equivalência da implicação ¬(¬p∨q)∨(p∨q) De Morgan (¬¬p∧¬q )∨( p∨q) Dupla Negação ( p∧¬q)∨( p∨q ) Distributiva ( p∨( p∨q))∧(¬q∨( p∨q)) Associativa ( p∨p∨q)∧(¬q∨p∨q) Idempotentes e identidade ( p∨q)∧p FNC Tabela-verdade p q p∨q p→q ¬(p→q) ¬(p→q)∨( p∨q) v v v v f v v f v f v v f v v v f v f f f v f f Focalizando as interpretações cujos valores-verdade de α são f , segundo o Procedimento, FNC( α ): p∨q h) ¬(p→¬q)∧( p∧q) Manipulação Algébrica ¬(p→¬q)∧( p∧q) Equivalência da implicação ¬(¬p∨¬q)∧( p∧q) De Morgan (¬¬p∧¬¬q)∧(p∧q) Dupla Negação ( p∧q)∧( p∧q) Associativa e p∧q FNC Tabela-verdade p q ¬q p→¬q ¬(p→¬q) p∧q ¬(p→¬q)∧( p∧q) v v f f v v v v f v v f f f f v f v f f f f f v v f f f Focalizando as interpretações cujos valores-verdade de α são f , segundo o Procedimento, FNC( α ): (¬p∨q)∧( p∨¬q)∧(p∨q) 10) Usando tanto o método da tabela-verdade quanto o de manipulação algébrica de fórmula via equivalência lógica, determine a FND equivalente a: a) ¬p→(q∧r ) Manipulação Algébrica ¬p→(q∧r ) Equivalência da Implicação ¬¬p∨(q∧r) Dupla Negação p∨(q∧r ) FNDTabela-verdade p q r ¬p q∧r ¬p→(q∧r ) v v v f v v v v f f f v v f v f f v v f f f f v f v v v v v f v f v f f f f v v f f f f f v f f Focalizando as interpretações cujos valores-verdade de α são v , segundo o Procedimento 1.2, FND( α ): ( p∧q∧r)∨( p∧q∧¬r )∨( p∧¬q∧r)∨( p∧¬q∧¬r )∨(¬p∧q∧r ) b) ¬q∧(q→r ) Manipulação Algébrica ¬q∧(q→r ) Equivalência da Implicação ¬q∧(¬q∨r ) Distributiva (¬q∧¬q)∨(¬q∧r ) Idempotentes ¬q∨(¬q∧r ) FND Tabela-verdade q r ¬q q→r ¬q∧(q→r ) v v f v f v f f f f f v v v v f f v v v Focalizando as interpretações cujos valores-verdade de α são v , segundo o Procedimento 1.2, FND( α ): (¬q∧r )∨(¬q∧¬r) c) ( p→q)∨¬p Manipulação Algébrica ( p→q)∨¬p Equivalência da Implicação (¬p∨q)∨¬p Associativa ¬p∨q∨¬p Idempotentes ¬p∨q FND Tabela-verdade p q ¬p p→q ( p→q)∨¬p v v f v v v f f f f f v v v v f f v v v Focalizando as interpretações cujos valores-verdade de α são v , segundo o Procedimento 1.2, FND( α ): ( p∧q)∨(¬ p∧q )∨(¬p∧¬q) d) (¬p∧q)∨q Manipulação Algébrica (¬p∧q)∨q Lei da absorção q FND Tabela-verdade p q ¬p ¬p∧q (¬p∧q)∨q v v f f v v f f f f f v v v v f f v f f Focalizando as interpretações cujos valores-verdade de α são v , segundo o Procedimento 1.2, FND( α ): ( p∧q)∨(¬ p∧q ) e) ¬(p∧(q∨r )) Manipulação Algébrica ¬(p∧(q∨r )) De Morgan ¬p∨(q∨r ) Associativa ¬p∨q∨r FND Tabela-verdade p q r q∨r p∧(q∨r ) ¬(p∧(q∨r )) v v v v v f v v f v v f v f v v v f v f f f f v f v v v f v f v f v f v f f v v f v f f f f f v Focalizando as interpretações cujos valores-verdade de α são v , segundo o Procedimento 1.2, FND( α ): ( p∧¬q∧¬r )∨(¬p∧q∧r)∨(¬p∧q∧¬r )∨(¬p∧¬q∧r )∨(¬p∧¬q∧¬r ) f) p∨(q→r )→s Manipulação Algébrica p∨(q→r )→s Equivalência da Implicação p∨(¬q∨r )→s Equivalência da Implicação p∨¬(¬q∨r)∨s De Morgan p∨(¬¬q∧¬r )∨s Dupla Negação p∨(q∧¬r )∨s FND Tabela-verdade p q r s q→r p∨(q→r ) p∨(q→r )→s v v v v v v v v v v f v v f v v f v f v v v v f f f v f v f v v v v v v f v f v v f v f f v v v v v f f f v v f f v v v v v v f v v f v v f f v f v f f v f v f f f f v f f v v v v v f f v f v v f f f f v v v v f f f f v v f Focalizando as interpretações cujos valores-verdade de α são v , segundo o Procedimento 1.2, FND( α ): ( p∧q∧r∧s)∨(p∧q∧¬r∧s)∨(p∧¬q∧r∧s)∨(p∧¬q∧¬r∧s)∨(¬p∧q∧r∧s)∨(¬p∧q∧¬r∧s)∨... ...(¬p∧q∧¬r∧¬s )∨(¬ p∧¬q∧r∧s)∨(¬p∧¬q∧¬r∧s ) g) ¬(p∨q )∧(s→t ) Manipulação Algébrica ¬(p∨q )∧(s→t) Equivalência da Implicação ¬(p∨q )∧(¬s∨t) Equivalência da Implicação (¬p∧¬q)∧(¬s∨t) De Morgan (¬p∧¬q)∧(¬s∨t) Distributiva (¬s∧(¬p∧¬q ))∨(t∧(¬ p∧¬q)) Associativa (¬s∧¬p∧¬q)∨(t∧¬p∧¬q) FND Tabela-verdade p q s t p∨q ¬(p∨q ) s→t ¬(p∨q )∧(s→t) v v v v v f v f v v v f v f f f v v f v v f v f v v f f v f v f v f v v v f v f v f v f v f f f v f f v v f v f v f f f v f v f f v v v v f v f f v v f v f f f f v f v v f v f f v f f v f v f f f v v f v v v f f v f f v f f f f f v f v v v f f f f f v v v Focalizando as interpretações cujos valores-verdade de α são v , segundo o Procedimento 1.2, FND( α ): (¬p∧¬q∧s∧t)∨(¬ p∧¬q∧¬s∧t)∨(¬ p∧¬q∧¬s∧¬t) h) ¬(p∧q )∧( p∨q) Manipulação Algébrica ¬(p∧q )∧( p∨q) De Morgan (¬p∨¬q)∧( p∨q) Distributiva ( p∧(¬p∨¬q))∨(q∧(¬p∨¬q )) Distributiva (( p∧¬p)∨(p∧¬q))∨((q∧¬p)∨(q∧¬q)) Associativa ( p∧¬q)∨(q∧¬p) FND Tabela-verdade p q p∧q ¬(p∧q ) p∨q ¬(p∧q )∧( p∨q) v v v f v f v f f v v v f v f v v v f f f v f f Focalizando as interpretações cujos valores-verdade de α são v , segundo o Procedimento 1.2, FND( α ): ( p∧¬q)∨(¬p∧q)
Compartilhar