API tools faq
paste
Bananaware

lógica lista 1

Bananaware
May 4th, 2014
88
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.73 KB | None | 0 0
raw download clone embed print report
  1. // @author Jorge Luiz
  2. // lista 2: http://pastebin.com/AWJJXLjg
  3.  
  4. Exercício 1. (De [1]) Simplificar as seguintes fórmulas, removendo os parênteses
  5. desnecessários:
  6.  
  7. a) (p → (q → (p ˄ q)))
  8. (p → (q → p ˄ q))
  9. (p → q → p ˄ q)
  10. p → q → p ˄ q
  11.  
  12. b) ¬(p ˅ (p ˄ q))
  13. ¬(p ˅ p ˄ q )
  14.  
  15.  
  16. c) ¬(p ˄ (p ˅ q))
  17. Não podem ser removidos parênteses.
  18.  
  19.  
  20. d) ((p ˅ (p → q)) → q)
  21. (p ˅ (p → q) → q)
  22. p ˅ (p → q) → q
  23.  
  24.  
  25.  
  26. Exercício 2. (De [1]) Adicionar os parênteses às seguintes fórmulas para que fiquem de
  27. acordo com as regras de formação:
  28.  
  29. a) ¬p → q
  30. (¬p → q)
  31.  
  32.  
  33. b) p → q → r → p ˄ q ˄ r
  34. p → q → r → (p ˄ q) ˄ r
  35. p → q → r → ((p ˄ q) ˄ r)
  36. p → q → (r → ((p ˄ q) ˄ r))
  37. p → (q → (r → ((p ˄ q) ˄ r)))
  38. (p → (q → (r → ((p ˄ q) ˄ r))))
  39.  
  40.  
  41. c) p ˄ ¬q ˅ r ˄ s
  42. (p ˄ ¬q) ˅ r ˄ s
  43. (p ˄ ¬q) ˅ (r ˄ s)
  44. ((p ˄ ¬q) ˅ (r ˄ s))
  45.  
  46.  
  47. d) p ˄ ¬(p → ¬q) ˅ ¬q
  48. (p ˄ ¬(p → ¬q)) ˅ ¬q
  49. ((p ˄ ¬(p → ¬q)) ˅ ¬q)
  50.  
  51.  
  52.  
  53. Exercício 3. (De [1]) Dar o conjunto de subfórmulas das fórmulas a seguir. Notar que
  54. os parênteses implícitos são fundamentais para decidir quais são as subfórmulas:
  55.  
  56. a) (¬p → q)
  57. {¬p→q} U Subf(¬p) U Subf(q)
  58. {¬p→q, ¬p, q} U Subf(p)
  59. {¬p→q, ¬p, q, p}
  60.  
  61.  
  62. b) (p → (q → (r → ((p ˄ q) ˄ r))))
  63. // define: p→q→r→p˄q˄r = fB
  64. {fB} U Subf(p) U Subf(q→(r→((p˄q)˄r)))
  65. {fB, p, q→r→p˄q˄r} U Subf(q) U Subf(r→((p˄q)˄r))
  66. {fB, p, q→r→p˄q˄r, q, r→p˄q˄r} U Subf(r) U Subf((p˄q)˄r)
  67. {fB, p, q→r→p˄q˄r, q, r→p˄q˄r, r, p˄q˄r} U Subf(p˄q) U Subf(r)
  68. {fB, p, q→r→p˄q˄r, q, r→p˄q˄r, r, p˄q˄r, p˄q, r} U Subf(p) U Subf(q)
  69. {fB, p, q→r→p˄q˄r, q, r→p˄q˄r, r, p˄q˄r, p˄q, r, p, q}
  70. {fB, p, q→r→p˄q˄r, q, r→p˄q˄r, r, p˄q˄r, p˄q}
  71.  
  72.  
  73. c) ((p ˄ ¬q) ˅ (r ˄ s))
  74. // define: p˄¬q˅r˄s = fC
  75. {fC} U Subf(p˄¬q) U Subf(r˄s)
  76. {fC, p˄¬q, r˄s} U Subf(p) U Subf(¬q) U Subf(r) U Subf(s)
  77. {fC, p˄¬q, r˄s, p, ¬q, r, s} U Subf(q)
  78. {fC, p˄¬q, r˄s, p, ¬q, r, s, q}
  79.  
  80.  
  81. d) ((p ˄ ¬(p → ¬q)) ˅ ¬q)
  82. // define: p˄¬(p→¬q)˅¬q = fD
  83. {fD} U Subf(p˄¬(p→¬q)) U Subf(¬q)
  84. {fD, p˄¬(p→¬q), ¬q} U Subf(p) U Subf(¬(p→¬q)) U Subf(q)
  85. {fD, p˄¬(p→¬q), ¬q, p, ¬(p→¬q), q} U Subf(p→¬q)
  86. {fD, p˄¬(p→¬q), ¬q, p, ¬(p→¬q), q, p→¬q} U Subf(p) U Subf(¬q)
  87. {fD, p˄¬(p→¬q), ¬q, p, ¬(p→¬q), q, p→¬q, p, ¬q} U Subf(q)
  88. {fD, p˄¬(p→¬q), ¬q, p, ¬(p→¬q), q, p→¬q, p, ¬q, q}
  89. {fD, p˄¬(p→¬q), ¬q, p, ¬(p→¬q), q, p→¬q}
  90.  
  91.  
  92.  
  93. Exercício 4. (De [1]) Calcular a complexidade de cada fórmula do exercício anterior.
  94. Notar que a posição exata dos parênteses não influencia a complexidade da fórmula!
  95.  
  96. a) (¬p → q)
  97. 1 + |¬p| + |q|
  98. 1 + 1 + |p| + 1
  99. 1 + 1 + 1 + 1
  100. 4
  101.  
  102.  
  103. b) (p → (q → (r → ((p ˄ q) ˄ r))))
  104. 1 + |p| + |q→(r→((p˄q)˄r))|
  105. 1 + 1 + 1 + |q| + |r→((p˄q)˄r)|
  106. 1 + 1 + 1 + 1 + 1 + |r| + |(p˄q)˄r|
  107. 1 + 1 + 1 + 1 + 1 + 1 + 1 + |p˄q| + |r|
  108. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + |p| + |q| + 1
  109. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
  110. 11
  111.  
  112.  
  113. c) ((p ˄ ¬q) ˅ (r ˄ s))
  114. 1 + |p˄¬q| + |r˄s|
  115. 1 + 1 + |p| + |¬q| + 1 + |r| + |s|
  116. 1 + 1 + 1 + 1 + |q| + 1 + 1 + 1
  117. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
  118. 8
  119.  
  120.  
  121. d) ((p ˄ ¬(p → ¬q)) ˅ ¬q)
  122. 1 + |p˄¬(p→¬q)| + |¬q|
  123. 1 + 1 + |p| + |¬(p→¬q)| + 1 + |q|
  124. 1 + 1 + 1 + 1 + |p→¬q| + 1 + 1
  125. 1 + 1 + 1 + 1 + 1 + |p| + |¬q| + 1 + 1
  126. 1 + 1 + 1 + 1 + 1 + 1 + 1 + |q| + 1 + 1
  127. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
  128. 10
  129.  
  130.  
  131.  
  132. Exercício 5. (De [1]) Definir por indução sobre a estrutura das fórmulas a função
  133. atomos(A), que retorna o conjunto de todos os átomos que ocorrem na fórmula A. Por
  134. exemplo, atomos(p ˄ ¬(p → ¬q) ˅ ¬q) = {p, q}.
  135.  
  136. 1. Caso base: Se A = p, atomos(p) = {p} para toda fórmula atômica p
  137. 2. Caso A = ¬B, atomos(¬B) = atomos(B)
  138. 3. Caso A = B˄C, atomos(B˄C) = atomos(B) U atomos(C)
  139. 4. Caso A = B˅C, atomos(B˅C) = atomos(B) U atomos(C)
  140. 5. Caso A = B→C, atomos(B→C) = atomos(B) U atomos(C)
  141.  
  142. ou
  143.  
  144. 3. Para ○ E {˄,˅,→}, caso A = B○C, atomos(B○C) = atomos(B) U atomos(C)
  145.  
  146.  
  147.  
  148. Exercício 6. (De [1]) Classificar as fórmulas a seguir de acordo com sua satisfazibilidade,
  149. validade, falsificabilidade ou insatisfazibilidade:
  150.  
  151. a) (p → q) → (q → p)
  152.  
  153. p q p→q q→p (p→q)→(q→p)
  154. 0 0 1 1 1
  155. 0 1 1 0 0
  156. 1 0 0 1 1
  157. 1 1 1 1 1
  158.  
  159. satisfazível e falsificável
  160.  
  161.  
  162. b) (p ˄ ¬p) → q
  163.  
  164. p q ¬p p˄¬p (p˄¬p)→q
  165. 0 0 1 0 1
  166. 0 1 1 0 1
  167. 1 0 0 0 1
  168. 1 1 0 0 1
  169.  
  170. válida (e portanto satisfazível)
  171.  
  172.  
  173. c) ¬(p → p ˅ q)
  174. p q p˅q p→p˅q ¬(p→p˅q)
  175. 0 0 0 1 0
  176. 0 1 1 1 0
  177. 1 0 1 1 0
  178. 1 1 1 1 0
  179.  
  180. insatisfazível (e portanto falsificável)
  181.  
  182.  
  183. d) ((p → q) ˄ (r → q)) → (p ˅ r → q)
  184. p q r p˅r p→q r→q (p→q)˄(r→q) p˅r→q ((p→q)˄(r→q))→(p˅r→q)
  185. 0 0 0 0 1 1 1 1 1
  186. 0 0 1 1 1 0 0 0 1
  187. 0 1 0 0 1 1 1 1 1
  188. 1 0 0 1 0 1 0 0 1
  189. 0 1 1 1 1 1 1 1 1
  190. 1 0 1 1 0 0 0 0 1
  191. 1 1 0 1 1 1 1 1 1
  192. 1 1 1 1 1 1 1 1 1
  193.  
  194. válida (e portanto satisfazível)
  195.  
  196.  
  197.  
  198. Exercício 7. (Adaptado de [2]) Seja V uma valoração tal que V (p → q) = 1, o que
  199. pode-se concluir a respeito dos resultados da valoração V ((p ˅ r) → (q ˅ r))? E se
  200. V (p → q) = 0?
  201.  
  202. Resposta: 1.1 - Se V(p→q) = 1, então ou p = 0 ou p, q = 1.
  203. Se p = 0, então claramente a valoração de (p˅r)→(q˅r) será 1 a não ser que r = 1.
  204. Porém, se r = 1, então (p˅r) = 1 e (q˅r) = 1, portanto (p˅r)→(q˅r) = 1.
  205. 1.2 - Se p = 1, sabemos que q = 1 também, caso contrário V(p→q) seria 0.
  206. Portanto, se p = 1 e q = 1, claramente (p˅r) = 1 e (q˅r) = 1 e (p˅r)→(q˅r) = 1.
  207.  
  208. Conclusão: se V(p→q) = 1, então V((p˅r)→(q˅r)) também = 1. (consequência lógica)
  209.  
  210. 2 - Se V(p→q) = 0, então necessariamente p = 1 e q = 0.
  211. Neste caso, a valoração da fórmula depende da valoração de r. Demonstração:
  212. Para r = 0: ((p ˅ r) → (q ˅ r))
  213. ((1 ˅ 0) → (0 ˅ 0))
  214. 1 → 0
  215. 0
  216. Para r = 1: ((p ˅ r) → (q ˅ r))
  217. ((1 ˅ 1) → (0 ˅ 1))
  218. 1 → 1
  219. 1
  220.  
  221.  
  222.  
  223. Exercício 8. Sem usar tabela-verdade, argumente o porquê de (p ˄ q ˄ r ˄ s) → s ser
  224. uma tautologia.
  225.  
  226. Resposta: Pela definição de →, a única maneira de falsificar a fórmula é se (p˄q˄r˄s) = 1 e s = 0.
  227. Porém, para que (p˄q˄r˄s)=1, é necessário que s = 1.
  228. Como s não pode assumir os valores de 0 e 1 ao mesmo tempo, a fórmula é uma tautologia.
  229.  
  230.  
  231.  
  232. Exercício 9. Se A é uma tautologia então o que concluímos de ¬A? Argumente sobre isso.
  233.  
  234. Resposta: ¬A é insatisfazível, pois A ser uma tautologia implica que A = 1 para qualquer valoração.
  235. Se A = 1 para qualquer valoração e ¬1 = 0, então ¬A = 0 para qualquer valoração.
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!