fundamentos

Prévia do material em texto

Semana 1 – Conceitos Básicos: lógica formal
Pergunta 1:
Utilize as letras indicadas nos exercícios para representar os argumentos abaixo e prove a validade aplicando regras de inferência. 
Se Maria for assistir a uma série no canal de stream, não estudará para a prova, mas Maria deve estudar para a prova ou será reprovada. Logo, se Maria for assistir a uma série no canal de stream, ela será reprovada (A, B, C).
Resposta:
1. Se Maria for assistir a uma série no canal de stream, não estudará para a prova, mas Maria deve estudar para a prova ou será reprovada. Logo, se Maria for assistir a uma série no canal de stream, ela será reprovada. 
A: Maria vai assistir à série.
B: Maria estuda para a prova.
C: Maria é reprovada.
 
A → B′: se Maria for assistir à série no canal de stream, não estudará para a prova.
B∨C: Maria deve estudar para a prova ou será reprovada. 
A → C: se Maria for assistir à série no canal de stream, ela será reprovada. 
 (A → B′) ∧ (B ∨ C) → (A → C)
Podemos reescrever o argumento como:
(A → B′) ∧ (B ∨ C)∧ A → C)
Supondo que o argumento A é verdadeiro (hipótese), resta provar a validade de C.
 Uma sequência de demonstração é:
 
1. A → B′ hip
2. B ∨ C hip
3. A  hip
4. B′  1, 3, modus ponens
5. B’ → C 2, equivalência condicional. (B ∨ C⇔ B’→C)
6. C           4,5 modus ponens
Pergunta 2:
Utilize as letras indicadas nos exercícios para representar os argumentos abaixo e prove a validade aplicando regras de inferência.
Ou o carro não está em bom estado ou o cliente irá comprá-lo. Se o carro não estiver em bom estado, o vendedor perde a venda. O cliente não vai comprar o carro. Portanto, o vendedor vai perder a venda (A, B, C).
Resposta:
1. Ou o carro não está em bom estado ou o cliente irá comprá-lo.  Se o carro não estiver em bom estado, o vendedor perde a venda. O cliente não vai comprar o carro. Portanto, o vendedor vai perder a venda.
 A: o carro está em bom estado.
B: o cliente irá comprar o carro.
C: o vendedor perde a venda.
 A’ ∨ B: ou o carro não está em bom estado ou o cliente irá comprá-lo.
A’→C: se o carro não estiver em bom estado, o vendedor perde a venda.
 [(A’ ∨ B) ∧ (A’→C)∧B’]→C
Uma sequência de demonstração é:
 
1. (A’ ∨ B) hip
2. (A’→C)      hip
3. B’ hip
4. A → B 1, equivalência condicional. (A’ ∨ B⇔ A→B)
5. A’ 3,4, modus tollens
6. C        2,5, modus ponens
Pergunta 3:
Utilize as letras indicadas nos exercícios para representar os argumentos abaixo e prove a validade aplicando regras de inferência. 
A seleção da Alemanha era superior. Ou a seleção do Brasil não era a melhor de todas ou o técnico armou mal o time. O técnico não armou mal time, mas se a seleção do Brasil tinha o melhor time, a Seleção Brasileira era a melhor de todas. Portanto, a seleção do Brasil não tinha o melhor time e a seleção da Alemanha era superior (A, B, C, D).
Resposta:
A seleção da Alemanha era superior. Ou a seleção do Brasil não era a melhor de todas ou o técnico armou mal o time. O técnico não armou mal time, mas se a seleção do Brasil tinha o melhor time, a seleção Brasileira era a melhor de todas. Portanto, a seleção do Brasil não tinha o melhor time e a seleção da Alemanha era superior.
 A: a seleção da Alemanha era superior.
B: a seleção do Brasil era a melhor de todas.
C: o técnico armou mal o time.
D: a seleção do Brasil tinha o melhor time.
B’∨C: ou a seleção Brasileira não era a melhor de todas ou o técnico armou mal o time. 
C’∧(D→B): o técnico não armou mal time, mas se a seleção do Brasil tinha o melhor time, a Seleção Brasileira era a melhor de todas.
D’∧ A: a seleção do Brasil não tinha o melhor time e a seleção da Alemanha era superior.
 A∧(B’∨C)∧C’∧(D→B)→D’∧ A
 Uma sequência de demonstração é
1.A        hip.
2.(B’∨C)    hip
3.C’        hip
4.(D→B)    hip
1. B→C 2, equivalência condicional: B’ ∨ C⇔ B→C
2. B’ 3,5, modus tollens
3. B’→D’ 4, equivalência (D→B)⇔(B’→D’)
4. D’ 6,7 modus ponens
9. D’∧ A    1,8, conjunção.
Pergunta 4:
Utilize as letras indicadas nos exercícios para representar os argumentos abaixo e prove a validade aplicando regras de inferência. 
Se não for verdade que João vai viajar e Maria vai trabalhar, então alguém irá trabalhar. João não foi ao trabalho. Se alguém vai trabalhar, então João teria ido ao trabalho. Portanto, João vai viajar (A, B, C, D).
Resposta:
Se não for verdade que João vai viajar e Maria vai trabalhar, então alguém irá trabalhar. João não foi ao trabalho. Se alguém vai trabalhar, então João teria ido ao trabalho. Portanto, João vai viajar.
 A: João vai viajar
B: Maria vai trabalhar.
C: alguém irá trabalhar.
D: João foi ao trabalho.
 (A ∧ B)’ → C: se não for verdade que João vai viajar e Maria vai trabalhar, então alguém irá trabalhar. 
D’: João não foi ao trabalho.
C→ D: se alguém vai trabalhar, então João teria ido ao trabalho. 
A’: João vai viajar.
 [((A ∧ B)’ → C) ∧ D′ ∧ (C → D)] → A′
1.(A ∧ B)’ → C    hip.
1. D′     hip
2. (C → D) hip
3. C’     2,3, modus tollens
5.(A ∧ B)        1,4, modus tollens
6. A            5, simplificação.
Pergunta 5:
Utilize as letras indicadas nos exercícios para representar os argumentos abaixo e prove a validade aplicando regras de inferência. 
Ou as pessoas participam da votação ou a situação na cidade não vai melhorar. As pessoas não participam da votação ou as melhorias no cotidiano da cidade serão implementadas. Logo, se a situação na cidade melhorar, melhorias no cotidiano da cidade serão implementadas (A, B, C).
Resposta:
1. Ou as pessoas participam da votação ou a situação na cidade não vai melhorar. As pessoas não participam da votação ou as melhorias no cotidiano da cidade serão implementadas. Logo, se a situação na cidade melhorar, melhorias no cotidiano da cidade serão implementadas.
 A: as pessoas participam da votação.
B: a situação na cidade vai melhorar.
C: melhorias no cotidiano da cidade serão implementadas.
 A∨B’: ou as pessoas participam da votação ou a situação na cidade não vai melhorar.
A’∨C: as pessoas não participam da votação ou as melhorias no cotidiano da cidade serão implementadas. 
B→C: se a situação na cidade melhorar, melhorias no cotidiano da cidade serão implementadas.
 (A∨B’)∧(A’∨C)→(B→C)
Reescrevendo temos:     (A∨B’)∧(A’∨C)∧B→C
 1.(A∨B’)    hip
1.     (A’∨C)    hip
2. B hip
4.(B’∨A’)    1, comutatividade
1. B→A 4, equivalência condicional (B’ ∨ A⇔ B→A)
2. A 3,5, modus ponens
3. A→C 2, equivalência condicional (A’ ∨ C⇔ A→C)
8. C        6,7 modus ponens
Semana 2 – Logica de Predicados
1. Usando os símbolos de predicados abaixo e os quantificadores apropriados, escreva cada frase em português como uma fbf predicada. 
 
C(x): x é um cachorro
G(x): x é um gato
B(x, y): x faz mais bagunça do que y
 
  a. Qualquer gato faz mais bagunça do que qualquer cachorro.
  b. Nenhum cachorro faz mais bagunça do que todos os gatos. 
  c. Só cachorros são mais bagunceiros do que gatos.
  d. Todos os cachorros são mais bagunceiros do que algum gato.
Resposta
a. Qualquer gato faz mais bagunça do que qualquer cachorro. Se uma coisa é cachorro e outra é gato, então o gato faz mais bagunça do que o cachorro. (∀x)(∀(y)(C(x) ∧ G(y) → B(x, y))
b. Nenhum cachorro faz mais bagunça do que todos os gatos. Não existe um cachorro que faz mais bagunça do que todos os gatos. Negar que se existe um cachorro que para todo gato, então o cachorro faz mais bagunça que o gato. [(∃(x)(C(x) ∧ (∀(y)(G(y) → B(x, y)))]′ ou (∀(x)(C(x) → (∃(y)(G(y) ∧ [B(x, y)]′))
c. Só cachorros são mais bagunceiros do que gatos. Apenas cachorros são mais bagunceiros do que gatos. Lembre-se: o consequente vem depois do advérbio (∀x)(∀y)(B(x,y)∧G(y)→C(x))
d. Todos os cachorros são mais bagunceiros do que algum gato. (∀(x)(C(x) → (∃(y)(G(y) ∧ [B(x, y))) ou (∀(x)(∃(y)(C(x) → (G(y) ∧ B(x, y)))
2. Prove que os argumentos abaixo são válidos
 
1. (∀x)([A(x)]’ ∨ B(x)) ∧ (∀x)([A(x)]’ → [C(x)]’) → (∀x)(B(x) ∨ C’(x))
2. (∀x)(A(x) → [B(x)]′)  ∧ (∃x)(C(x) ∧ A(x)) → (∃x)(C(x) ∧ [B(x)]′)
3. (∀x)A(x) → C(x)) ∧ [(∀x)([A(x)]’ ∨ [B(x)]’) ]’ ∧ (∀x)(D(x)′ → B(x)′) → (∃x)(D(x) ∧ C(x))
 
Algumas outras regras de inferência da lógica proposicionalpodem ser úteis:
 
Outras regras são apresentadas na tabela 1.14 (Links para um site externo)Links para um site externo, página 34, do material-base: “Fundamentos Matemáticos para Ciência da Computação” de Judith L. Gersting.
Resposta
a. (∀x)([A(x)]’ ∨ B(x)) ∧ (∀x)([A(x)]’ → [C(x)]’) → (∀x)(B(x) ∨ [C(x)]’)
1.(∀x)([A(x)]’ ∨ B(x)) hip
2.(∀x)([A(x)]’ → [C(x)]’) hip
3. [A(u)]’∨ B(u) 1, particularização universal
4. [A(u)]’ → [C(u)]’ 2, particularização universal
5. B(u) ∨ [A(u)]’ 3, comutatividade
6. [B(u)]’ → [A(u)]’ 4, condicional
7. [B(u)]’ → [C(u)]’ 4,6, inferência R →T, T→S temos R→S
8. [B(u)] ∨ [C(u)]’ 7, condicional
9. (∀x)(B(x) ∨ [C(x)]’) 8, generalização universal
b. (∀x)(A(x) → [B(x)]′) ∧ (∃x)(C(x) ∧ A(x)) → (∃x)(C(x) ∧ [B(x)]′)
1. [(∀x)(A(x) → [B(x)]’) hip
2. (∃x)(C(x) ∧ A(x)) hip
3. A(u) → [B(u)]′ 1, particularização universal
4. C(u)∧A(u) 2, particularização existencial
5. C(u) 4, simplificação
6. A(u) 4, simplificação
7. [B(u)]’ 3,6, modus ponens
8. C(u)∧[B(u)]’ 5,7, conjunção
9 .(∃x)(C(x) ∧ [B(x)]′) 8, generalização existencial
c. (∀x)(A(x) → C(x)) ∧ [(∀x)([A(x)]’ ∨ [B(x)]’) ]’ ∧ (∀x)(D(x)′ → B(x)′) → (∃x)(D(x) ∧ C(x))
1. (∀x)A(x) → C(x)) hip
2. [(∀x)([A(x)]’ ∨ [B(x)]’) ]’ hip
3. (∀x)(D(x)′ → B(x)′) hip
4. (∃x)([A(x)]’ ∨ [B(x)]’)’ 2, [ (∃x)A(x) ] ’ ⇔ (∀x)[A(x)]’
5. (∃x)(A(x)∧ B(x)) 4, De Morgan
6. A(u)∧ B(u) 5, particularização existencial
7. A(u) 6, simplificação
8. A(u) → C(u) 1, particularização universal
9. C(u) 7,8, modus ponens
10. D(u)′ → B(u)′ 2, particularização universal
11. D(u) ∨ B(u)′ 10, condicional
12. B’(u)∨ D(u) 11, comutatividade
13. B(u) → D(u) 12, condicional
14. B(u) 6, simplificação
15. D(u) 13, 14, modus ponens
16. D(u)∧ C(u) 9,15, conjunção
17. (∃x)(D(x) ∧ C(x)) 16, generalização existencial.
Observe que nas linhas 10 a 13 fizemos uso da seguinte equivalência: R → T ⇔ T ’→ R’
que segue de: R → T ⇔ R ’∨ T ⇔ T∨R’ (comutatividade) ⇔ T ’→ R’
Logo, R → T ⇔ T ’→ R’
Assim, poderíamos ter simplificado a demonstração fazendo:
8. A(u) → C(u) 1, particularização universal
9. C(u) 7,8, modus ponens
10. D(u)′ → B(u)′ 2, particularização universal
11. B(u) → D(u) 10, (R → T) ⇔ (T ’→ R’)
12. B(u) 6, simplificação
13. D(u) 11, 12, modus ponens
14. D(u)∧ C(u) 9,13, conjunção
15. (∃x)(D(x) ∧ C(x)) 14, generalização existencial
Semana 3 – Técnica de Demonstração