Baixe o app para aproveitar ainda mais
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
Compartilhar