L ogica Computacional Gabarito da Primeira Prova
Transcrição
L ogica Computacional Gabarito da Primeira Prova
gica Computacional Lo Gabarito da Primeira Prova picos: To gica proposicional Lo ^ ntica e Deduc ~o Sema a ^ncias Exatas, Universidade de Bras Instituto de Cie lia 05 de outubro de 2009 n Prof. Mauricio Ayala-Rinco ~ o natural Deduc a 1. (4.0 pontos) Considere a seguinte deduca~o 1 da regra de contra posica~o: [¬q] p ∨ ¬p z [p]y [p → q]u q →e ¬e ⊥ ¬p ⊥e ¬q → ¬p → i, z ∨e, x, y → i, u [¬p]x ¬q → ¬p → i, ∅ ¬q → ¬p (p → q) → (¬q → ¬p) (a) (2.0) Complete a deduca~o, apresentando uma arvore de deduca~o natural da lei do meio excludo; i.e., uma deduca~o de p ∨ ¬p. R/ [p]m [¬(p ∨ ¬p)]l p ∨ ¬p ∨i ⊥ ¬p ¬i, m [¬(p ∨ ¬p)]l p ∨ ¬p ∨i ¬e ⊥ PBC, l p ∨ ¬p (b) (2.0) Apresente uma arvore de deduca~o natural 2 ¬e do recproco: ` (¬q → ¬p) → (p → q ) R/ [p] q ∨ ¬q [q]x z p → q → i, ∅ p→q (¬q → ¬p) → (p → q) [¬q → ¬p]u [¬q]y ¬p →e ¬e ⊥ q ⊥e p → q → i, z ∨e, x, y → i, u 2. (2.0 pontos) Considere a seguinte agrumentaca~o sobre a correca~o da Lei de Peirce tomada da Wikipedia: Para mostrar que a implicac~ao ((A → B ) → A) → A e valida sup~oe-se, por absurdo, que ela e falsa, isto e, ¬(((A → B ) → A) → A). Portanto, ((A → B ) → A) e verdadeira e A e falsa, de donde, A → B e falsa, e portanto A e verdadeira, o que resulta em um absurdo. Conclui-se que ((A → B ) → A) → A. Construir-se-a uma arvore de deduca~o natural traduzindo a argumentaca~o precedente. P.ex., \Portanto, ((A → B ) → A) e verdadeira e A e falsa, de donde, A → B e falsa" pode ser expressa na seguinte deduca~o, 1 : [A → B ]u (A → B ) → A A →e ¬A ¬e ⊥ ¬i, u ¬(A → B ) E a seguir, \, e portanto A e verdadeira", na seguinte arvore de deduca~o, 2 : [¬A]v 1 ¬(A → B ) ⊥ A ¬B → ¬A ( 2 item 1b A→B PBC, v → i, ∅ ) ¬e Utilizando as deduco~es 1 e 2 e deduco~es 3 e 4 de que \se ¬(((A → B ) → A) → A) ent~ao ((A → B ) → A) e verdadeira e A e falsa", a saber: [¬(((A → B ) → A) → A)]w 3 (A → B ) → A e [¬(((A → B ) → A) → A)]w 4 ¬A Pode-se obter a deduca~o da Lei de Peirce, por contradica~o: [¬(((A → B ) → A) → A)]w 4 ¬A [¬(((A → B ) → A) → A)]w [¬(((A → B ) → A) → A)]w 3 4 (A → B ) → A ¬A 1 ¬(A → B ) 2 ⊥ ((A → B ) → A) → A PBC, w A ¬e Complete a deduca~o construndo arvores de deduca~o natural para (a) (1.0) 3 e R/ [¬(((A → B ) → A) → A)]w ⊥ [¬((A → B ) → A)]x → i, ∅ ¬A → ¬((A → B ) → A) 2 (1b) ((A → B ) → A) → A ¬e PBC, x (A → B ) → A (b) (1.0) 4 . R/ [¬(((A → B ) → A) → A)]w [A]y ((A → B ) → A) → A ⊥ ¬i, y ¬A → i, ∅ ¬e ^ ntica Sema 3. (4.0 pontos) (a) (1.0) Construa uma formula em forma normal conjuntiva equivalente a Lei de Peirce ((A → B ) → A) → A Utilize os algoritmos especcos para esta tarefa descritos no texto da disciplina. R/ CNF(NNF(IMPL FREE(((A → B ) → A) → A))) = . . . (todos os passos devem ser includdos na resposta) CNF(NNF(¬(¬(¬A ∨ B ) ∨ A) ∨ A) . . . (todos os passos devem ser includdos na resposta) CNF(((¬A ∨ B ) ∧ ¬A) ∨ A) . . . (todos os passos devem ser includdos na resposta) (¬A ∨ B ∨ A) ∧ (¬A ∨ A) (b) (3.0) Utilize a tecnica de solucionador SAT para demonstrar que a Lei de Pierce e valida; i.e., demonstre que a negaca~o da Lei de Pierce e insatisfazvel: i. (1.0) Transforme a negaca~o da Lei de Pierce numa formula equivalente no fragmento negativo-conjuntivo da logica proposicional, utilizando o operador T ; R/ T (¬(((A → B ) → A) → A)) = ... ¬¬(T ((A → B ) → A) ∧ ¬A) = ... ¬¬(¬(T (A → B ) ∧ ¬A) ∧ ¬A) = ... ¬¬(¬(¬(A ∧ ¬B ) ∧ ¬A) ∧ ¬A) ii. (1.0) Construa um DAG para esta formula; R/ Veja Figura 1. iii. (1.0) Utilizando a tecnica de solucionadores SAT, demonstre que esta formula e insatisfazvel. R/ Veja Figura 2. ¬ ¬ A ∧* }} ** } } ** }} ** }} ** ¬ ** ** ** ** ∧ PPP PPP ** }} } P PPP * }} P } PPP * }} ¬ ¬ rr rr r r rr rr r r ∧ rr AAA rrrr AArr rA rr AA r r r r ¬ rrrr r r rrr rrr B Figure 1: DAG para ¬¬(¬(¬(A ∧ ¬B ) ∧ ¬A) ∧ ¬A) {1 : >}¬ {2 : F }¬ {3 : >}∧ {4 : {5 : q qq qq q qq qq {6 : F }¬ 22 22 22 22 22 >}¬ 22 22 22 22 F }∧ VV 22 VVVV 22 VVVV 22 VVVV VVVV 2 VV qq qq qq q q qq k kkk kkk k × k k kkk kkk k k k {6 : F }∧ kkk NNN kkk w k k w N NNN kkkk ww kkkNNNN ww k w k k N w k k w w kk ¬ kkk ww k k w ww kkkkkk w ww kkk ww kkk {5 : F }A {4 : >}¬ B Figure 2: Vericaca~o da (in)satisfazibilidade de ¬¬(¬(¬(A ∧ ¬B ) ∧ ¬A) ∧ ¬A)