Lógica-AP2-2010-2

Prévia do material em texto

Segunda Avaliac¸a˜o Parcial
Prof. Davi Romero de Vasconcelos
29 de novembro de 2010
SIN015 – Lo´gica para Computac¸a˜o Questa˜o 1 1.5 pontos
Nome: pontos
Prove ou refute os itens abaixo utilizando o sistema de Tableau Semaˆntico.
Caso o item seja refutado, apresente todos os contra-exemplos de acordo com o
tableau apresentado.
1. A→ (B ∨ C), C → D ` (A→ B) ∨ (A→ D)
2. A→ C,B → C ` (A ∧B) → C
3. ¬(A→ (B → C)) ` B ∧ (A ∧ ¬C)
1
SIN015 – Lo´gica para Computac¸a˜o Questa˜o 2 3.5 pontos
Nome: pontos
1. (0.5 pontos) Dizemos que um ve´rtice v e´ uma fonte se nenhum arco do
grafo tem v como destino. Expresse o conceito de fonte como uma fo´mula.
2. (0.5 pontos) Dizemos que um ve´rtice v e´ um sumidouro se nenhum arco
do grafo tem v como origem. Expresse o conceito de sumidouro como uma
fo´mula.
3. (1.25 pontos) Mostre que as fo´rmulas definidas anteriormente (sumidouro
e fonte) sa˜o satisfat´ıveis.
4. (1.25 pontos) Mostre que as fo´rmulas definidas anteriormente (sumidouro
e fonte) sa˜o falsifica´veis.
2
SIN015 – Lo´gica para Computac¸a˜o Questa˜o 2 3.5 pontos
Nome: pontos
3
SIN015 – Lo´gica para Computac¸a˜o Questa˜o 3 3.0 pontos
Nome: pontos
Prove, utilizando o sistema de Deduc¸a˜o Natural, os itens abaixo.
1. ` ∃x(ϕ(x) → ψ) → (∀xϕ(x) → ψ), onde x 6∈ V L(ψ)
2. ` (∀xϕ(x) → ψ) → ∃x(ϕ(x) → ψ), onde x 6∈ V L(ψ)
3. ` ∀x(ϕ(x) → ψ) → (∃xϕ(x) → ψ), onde x 6∈ V L(ψ)
4
SIN015 – Lo´gica para Computac¸a˜o Questa˜o 4 2.0 pontos
Nome: pontos
Seja DN∧ um sistema de deduc¸a˜o natural que contenha apenas as regras de
introduc¸a˜o e eliminac¸a˜o do conectivo ∧. Defina uma func¸a˜o t que recebe uma
derivac¸a˜o e retorne o nu´mero de aplicac¸o˜es da regra de introduc¸a˜o do ∧. Abaixo
temos treˆs exemplos da func¸a˜o t aplicada a treˆs derivac¸o˜es diferentes.
t(A ∧B) = 0 t
(
A B
A ∧B
)
= 1 t

A B
A ∧B
A
 = 1
5