Segunda Lista de Exercício Lógica para Computação

Prévia do material em texto

Segunda Prova de Lo´gica
1 Explique em palavras informais a noc¸a˜o de derivac¸a˜o no ca´lculo de Hilbert
(Lo´gica Proposicional). Apresente os Teoremas de Corretude e de Completude e ex-
plique o que estes teoremas expressam.
2 Seja ϕ = ∀x(R(x) → ∃y(f(y) = x ∨ P (c, g(x, y)))). Apresente todas as sub-
formulas e todos os termos que ocorrem em ϕ.
3 Seja Σ = (f, g, h,R, P, c, d; ar) com ar(f) = ar(R) = 1, ar(g) = ar(h) = 2,
ar(P ) = 3. Apresente cinco Σ-termos sem varia´veis e duas Σ-fo´rmulas na˜o-atoˆmicas.
4 Seja Σ uma assinatura. Prove por induc¸a˜o nas fo´rmulas que toda Σ-fo´rmula tem
um nu´mero par de pareˆnteses.
5 Seja Σ = (R; ar), ar(R) = 2. Mostre que ϕ = ∃x∀yR(x, y) na˜o e´ consequeˆncia
lo´gica do conjunto
Φ = {∀xR(x, x),
∀x∀y∀z((R(x, y) ∧R(y, z))→ R(x, z)),
∀x∀y((R(x, y) ∧R(y, x))→ x = y)},
ou seja, Φ 1 ϕ.
6 Prove: ∀x(ϕ ∨ ψ) 
 ∃xϕ ∨ ∀xψ. (Relembre que uma disjunc¸a˜o se prova, por
ex., mostrando que a segunda parte e´ verdadeira se a primeira e´ falsa.)
7 Seja Σ = (R) onde R e´ um sı´mbolo de relac¸a˜o com ar(R) = 2. Apresente um
conjunto (infinito) Φ de Σ-sentenc¸as tal que para qualquer Σ-estruturaM:M � Φ sse
RM ⊆ M ×M e´ uma relac¸a˜o de equivaleˆncia com um nu´mero infinito de classes de
equivaleˆncia.
8 Prove: ¬∀xϕ ≡ ∃x¬ϕ.
9 Seja Σ = (R; ar), ar(R) = 2, ϕ = ∃x∀yR(x, y). Apresente duas Σ-estruturas
M,M′ tais queM � ϕ eM′ 2 ϕ.
10 (3P) Prove ou refute dando um contra-exemplo:
(i) ∀x(ϕ ∧ ψ) ≡ ∀xϕ ∧ ∀xψ.
1
(ii) ∃x(ϕ ∧ ψ) ≡ ∃xϕ ∧ ∃xψ.
11 Seja Σ = (+, S, 0) e A = (N,+A, SA, 0A) a Σ-estrutura dos nu´meros natu-
rais com adic¸a˜o, func¸a˜o de sucessor, e zero. Seja I = (A, β), onde β : V → N e´
qualquer valorac¸a˜o. Apresente dois Σ-termos diferentes t1, t2 sem varia´veis tais que
I(t1) = 4 = I(t2).
12 Seja Σ = (<) e Φ o conjunto das Σ-sentenc¸as que axiomatizam as ordens
lineares, ou seja, Φ conte´m exatamente as seguintes treˆs sentenc¸as:
∀x¬(x < x),
∀x∀y∀z(x < y ∧ y < z → x < z),
∀x∀y(x < y ∨ x = y ∨ y < x).
Prove que ψ = ∀x∀y(x < y → ∃z(x < z ∧ z < y)) e´ independente de Φ, isto
e´, Φ 1 ψ e Φ 1 ¬ψ. (Dica: Voceˆ deve encontrar uma Σ-estrutura que serve como
contra-exemplo da relac¸a˜o Φ 
 ψ e uma outra Σ-estrutura que e´ contra-exemplo de
Φ 
 ¬ψ.)
2