Exercícios Resolvidos de Lógica Matemática

1. Exemplos de Cálculo Proposicional

1. Dê exemplo de uma fórmula φ do Cálculo Proposicional que tenha exatamente três subfórmulas e tal que var((p0 ∨ p1)[φ/p1]) = {p0, p1}.
R: φ := (p1 ∨ ¬p1), subf(φ) = {p1, ¬p1, (p1 ∨ ¬p1)}, (p0 ∨ p1)[φ/p1] = p0 ∨ (p1 ∨ ¬p1), var = {p0, p1}.

2. Dê exemplo de uma fórmula φ do Cálculo Proposicional cujos conectivos estejam no conjunto {¬, ∧} e tal que φ ∧ (p0 ∨ p1) seja uma contradição.
R: φ := (¬p0 ∧ ¬p1), os conectivos de φ pertencem a {¬, ∧} e φ ∧ (p0 ∨ p1) é uma contradição.

3. Dê exemplo de uma valoração v0 que mostre que: p0 → p1, p1 → p2 ⊭ p0 ∨ p2.
R: v0(p0)=0, v0(p1)=0, v0(p2)=1, pois v0(p0→p1)=1 e v0(p1→p2)=1 mas v0(p0∨p2)=1, logo p0→p1, p1→p2 ⊭ p0∨p2.

4. Indique um conjunto de fórmulas proposicionais Γ que seja maximalmente consistente e tal que {p1 ↔ p2, ¬p1} ⊂ Γ.
R: Γ = {¬p1, ¬p2, p1 ↔ p2} ∪ {todas as tautologias do Cálculo Proposicional}.

2. Estruturas Lógicas e Linguagens

Considere o tipo de linguagem L = ({c, f}, {P, =}, N) em que N(c) = 0, N(f) = 2, N(P) = 1 e N(=) = 2, e considere a L-estrutura E = (Z, ) tal que: c = 1, f : Z² → Z tal que f(z1, z2) = z1 + z2, P = {z ∈ Z | z = 2z0, p/ alg. z0 ∈ Z} = {(z1, z2) ∈ Z² | z1 = z2}.

Dê exemplo de uma atribuição a0 em E tal que f(c, x0)[a0]E = f(x1, f(c, c))[a0]E.
R: a0(x0)=1 e a0(x1)=0, pois f(c,x0)[a0]=1+1=2 e f(x1,f(c,c))[a0]=0+(1+1)=2.

Indique o número de L-estruturas cujo domínio é {0, 1}.
Existem 2 escolhas p/ c, 4 escolhas p/ P ⊆ {0,1}, 16 funções possíveis f : {0,1}² → {0,1} e a relação = é fixa, logo o número de L-estruturas é 2 × 4 × 16 = 128.

3. Substituição e Forma Normal

Dê exemplo de um L-termo t tal que x0 não seja substituível sem captura de variáveis por t em ψ = ∀x1∃x2¬(x0 + x1 < x2).
t := x1, pois x0 ocorre livre no alcance de ∀x1 em ψ e x1 ∈ VAR(t), logo a substituição provoca captura de variáveis.

Dê exemplo de uma L-fórmula φ que seja uma forma normal prenexa tal que φ ⇔ (x0 = 0 ∧ ¬∃x0 x0 < 0).
φ := ∀x1 (x0 = 0 ∧ ¬(x1 < 0)), que está em forma normal prenexa e é logicamente equivalente a (x0 = 0 ∧ ¬∃x0 x0 < 0).

4. Provas e Deduções

Prova por indução estrutural: Se φ ∈ FCP e os conectivos de φ pertencem a BIN = {∧, ∨, →, ↔}, então v1(φ) = 1 (onde v1(pi) = 1).

Justificação de Forma Normal Disjuntiva (FND): Para a fórmula (p0 ↔ p1) ∨ ¬p1, utilize o método da tabela de verdade para identificar os casos onde a fórmula resulta em 1.

Demonstração: Se Γ ∪ {φ} é consistente e Γ ⊨ φ → ψ, então ψ não é uma contradição.

Validade em E: Mostre que ∀x1 ((P(x1) ∧ P(x2)) → P(f(x1, x2))) é válida em E, dado que a soma de dois inteiros pares é um inteiro par.

Demonstração de equivalência: (∃x σ) ∧ φ, ∃x ψ ⊢ ∃x(φ ∧ ψ), dado x ∉ LIV(φ).

5. Forma Normal Prenexa de L_Arit

Pretende-se dar um exemplo de uma forma normal prenexa logicamente equivalente à L_Arit-fórmula (¬∃x1 (x0 = x1)) ∧ ∃x0 (x0 < 0).

• Renomeação: (¬∃x1 (x0 = x1)) ∧ ∃x2 (x2 < 0).
• Negação: ∀x1 ¬(x0 = x1) ∧ ∃x2 (x2 < 0).
• Forma Final: ∀x1 ∃x2 (¬(x0 = x1) ∧ (x2 < 0)).