Lista Lógica

Prévia do material em texto

Lista 2 de exercı́cios de lógica
7 de abril de 2022
1 Prove o seguinte (sem tabela verdade): ϕ ∨ (ψ ∧ χ) ≡ (ϕ ∨ ψ) ∧ (ϕ ∨ χ),
ϕ → ψ → χ ≡ ϕ ∧ ψ → χ, (ϕ ∧ ψ) ∨ ψ ≡ ψ, (ϕ ∨ ψ) ∧ ψ ≡ ψ. (Para mostrar
a primeira regra de absorção, relembre os métodos de demonstração apresentados na
primiera aula, a dizer, demonstração por casos e a demonstração de uma disjunção.)
2 Seja Fm∧ o menor conjunto que contém todas as variáveis V e é fechado sob
a condição seguinte: se ϕ,ψ ∈ Fm∧, então (ϕ ∧ ψ) ∈ Fm∧. Prove por indução
que nenhuma fórmula de Fm∧ é válida. Por que isso implica que {∧} não é base de
conectivos?
3 Desenvolva uma FND e uma FNC de
ϕ = p→ ¬(q → r),
ψ = x ∨ y → ¬x,
ξ = x ∧ y → ¬x,
δ = ¬(p∧ q)→ p→ ¬p, respectivamente. Verifique suas respostas usando o software
em Haskell disponibilizada para a disciplina. (Note que o código Haskell não aplica
estratégicas ‘inteligentes’ para gerar formas normais mais curtas ou eficientes, portanto
os resultados podem ser sintaticamente diferentes porém logicamente equivalentes.)
4 No código Haskell disponibilizado para a disciplina, a função ‘subformulas’ gera
uma lista de todas as subfórmulas de uma dada fórmula ϕ conforme Definição 3.2 do
script. Porém, essa lista pode conter repetições de fórmulas (se uma subfórmula ocorre
n vezes em ϕ, então ela vai ocorrer n vezes na lista). Modifique a função Haskell
usando a função listToSet para garantir que toda subfórmula é apresentada apenas uma
vez (listToSet transforma uma lista qualquer numa lista sem repetições de elementos).
Optativo: Consulte textos sobre Haskell e tente entender como funcionam as funções
insert2 e listToSet.
5 Optativo: Projete uma função Haskell que para qualquer fórmula dada ϕ gera
uma lista de todas as variáveis que ocorrem em ϕ, isto é, implemente a função recursiva
var(ϕ) da Definição 3.6 do script.
1