lista1-Prop-2014-2

Prévia do material em texto

CIC 117366 Lógica Computacional 1 - Turma A - 2014/2 22 de agosto de 2014
Lista: Lógica Proposicional
Sintaxe, Semântica e Dedução Natural
Em adição aos exerćıcios que aparecem nas notas de aula, faça os listados a seguir. Nas suas
derivações, sempre indique qual regra dedutiva é utilizada em cada um dos passos.
1. Nos seguintes exerćıcios use a prova por indução na estrutura das fórmulas bem for-
madas do cálculo proposicional.
(a) Demonstre por indução na estrutura das fórmulas, que uma fórmula bem formada
é balanceada, no sentido de que o número de parênteses abertos ”(”é igual ao de
fechados ”)”, isto é, |ϕ|( = |ϕ|).
(b) Demonstre que para todo prefixo s de uma fórmula bem formada t, vale |s|( ≥ |s|).
(c) Demonstre que a palavra vazia não é uma fórmula bem formada.
(d) Demonstre que uma fórmula bem formada não tem prefixos próprios que são
também fórmulas: Se ϕ é uma fórmula bem formada e s é prefixo próprio de ϕ
então s não pode ser uma fórmula bem formada.
2. Prove os sequentes a seguir utilizando apenas o cálculo de dedução natural para lógica
proposicional intuicionista:
(a) φ ∧ ψ ` φ.
(b) ¬(φ ∨ ψ) ` (¬φ ∧ ¬ψ).
(c) ¬¬(φ ∧ ψ) ` ¬¬φ ∧ ¬¬ψ.
(d) ¬(φ ∨ ψ) a` ¬φ ∧ ¬ψ.
3. Construa derivações para os sequentes a seguir e indique se foi utilizada a lógica intui-
cionista ou clássica:
(a) (φ→ ψ) ∧ (δ → ψ) ` (φ ∧ δ)→ ψ.
(b) (φ→ ψ) ` (¬ψ → ¬φ).
(c) ` (φ ∨ ψ)↔ ¬(¬φ ∧ ¬ψ).
(d) ` (¬¬φ→ ¬¬ψ)→ ¬¬(φ→ ψ).
(e) (φ ∧ (ψ ∨ δ)) ` ((φ ∧ ψ) ∨ (φ ∧ δ)).
4. Construa provas para todas as variantes da regra (MT):
φ→ ±ψ ∓ ψ
∓φ
(MT1 e 2)
Indique quais regras são da lógica clássica e quais da lógica intuicionista proposicional.
1
5. Construa provas para todas as variantes da regra (CP):
±/± φ→ ±/∓ ψ
∓/± ψ → ∓/∓ φ
(CP1,2,3 e 4)
Indique quais regras são da lógica clássica e quais da lógica intuicionista proposicional.
6. Construa a tabela de verdade e verifique se os sequentes são tautológicos, satisfat́ıveis
ou insatisfat́ıveis:
(a) q → (p→ (p→ (q → p)))
(b) (p→ q)→ ((r → s)→ (p ∧ r → q ∧ s))
(c) φ→ ¬φ.
(d) (φ ∧ ψ)→ (ψ ∨ φ).
(e) φ ∧ ¬φ.
(f) ((φ→ ψ) ∨ (φ→ δ)) ∧ (¬φ ∨ γ).
7. Pela definição de consequência lógica, mostre que ¬φ → ¬ψ é consequência lógica de
ψ → φ.
8. Explique por que toda fórmula tautológica é também satisfat́ıvel e modele três exemplos
de fórmulas satisfat́ıveis que não são tautológicas, apresentando suas tabelas-verdade.
2