01/04/2015


Lógica
Ruan Carvalho

Domínio dos valores verdade
◦ 0: falso
◦ 1: verdade

Atribuir um valor verdade para cada
expressão
¬φ, φ^Ψ, φvΨ, φ⟶Ψ
◦ Como interpretar ¬φ, dado φ?
◦ Como interpretar φ□Ψ, dados φ e Ψ?

v^ : PROP ⟶ BOOL

v^(φ) = v (φ), se φ for atômica
v^(¬φ) = 1 - v^(φ)
v^(φ^Ψ) = MIN(v^(φ), v^(Ψ))
v^(φvΨ) = MAX(v^(φ), v^(Ψ))
v^(φ⟶Ψ) = ≤(v^(φ), v^(Ψ))
Seja v(A)=1, v(B)=0 e v(C)=1

Seja v uma valoração
v^(A^(BvC))
v^(¬A v (B^C))
v^((AvC) ⟶(B^A))

Dizemos que v satisfaz φ quando v^(φ) = 1

Caso contrário, dizemos que v refuta φ
Função v
◦ Recebe um átomo
◦ Retorna um valor-verdade


Qual o significado de uma expressão?




Função v^
◦ Extende v para PROP




1
01/04/2015

φ é satisfatível quando existe valoração que a
satisfaça


φ é insatisfatível quando não existe valoração
que a satisfaça

v satisfaz Γ quando v^(α1)=v^(α2)= ... = v^(αn)=1

Γ é satisfatível quando existe v que o satisfaz

φ é refutável quando existe valoração que a
refute

φ é tautologia quando não existe valoração
que a refute

Γ1 = {Av¬B, A^(B⟶C), ¬B}

Γ2 = {A⟶B, ¬Av¬B, A}

Γ3 = {A⟶B, A, ¬B}

Quando A é uma tautologia escrevemos:
Seja Γ = {α1, α2, ..., αn} um conjunto de
sentenças
◦ Caso contrário, é insatisfatível

φ é consequência lógica de Γ quando

Γ ⊨φ

Exemplos
◦ Toda valoração que satisfaz φ também satisfaz Γ
◦
◦
◦
◦
◦
{A, A⟶B} ⊨ B
{A⟶B, ¬B} ⊨ ¬A
{A, B} ⊨ A^B
{A^B, A⟶C, (B^E)⟶D} ⊨ (C^D)v¬E
{A⟶B} ⊨ ¬B⟶¬A
◦ ⊨A

Prove que A é tautologia sse ¬A for
insatisfatível

Γ ⊨ φ sse Γ∪{¬φ} for insatisfatível

φ é satisfatível sse ¬φ for refutável
2