Completude e integridade dos sistemas dedutivos

Integridade e completude dum sistema dedutivo D
Dado um conjunto Σ de premissas e uma conclus˜o φ: a Integridade Se existe uma dedu¸˜o de φ com premissas Σ, i.e Σ D φ, ca ent˜o a conclus˜o φ ´ consequˆncia semˆntica de Σ, i.e Σ |= φ. Em a a e e a particular, se D φ ent˜o φ ´ uma tautologia (|= φ) . a e
Completude Se φ ´ consequˆncia semˆntica de Σ, i.e Σ |= φ, ent˜o existe e e a a uma dedu¸˜o de φ com premissas Σ, i.e Σ D φ. Em particular, se φ ´ ca e uma tautologia (|= φ) ent˜o D φ. a Departamento de Ciˆncia de Computadores da FCUP — LC — Aula 6 e 1

Integridade do sistema de dedu¸˜o ca natural N D
Proposi¸˜o 6.1. Se Σ ca φ ent˜o Σ |= φ a Dem. Suponhamos que temos uma dedu¸˜o de φ, φ1, . . . , φn = φ. Vamos ca mostrar que em cada passo a f´rmula que a´ ocorre ´ consequˆncia o ı e e semˆntica das premissas (ou hip´teses) que a´ s˜o assumidas. a o ı a
Provamos por redu¸˜o ao absurdo: Suponhamos que existe um passo ca p que cont´m uma f´rmula que n˜o ´ consequˆncia semˆntica das e o a e e a premissas assumidas em p. E seja p o primeiro desses passos . Vamos ver que qualquer que seja a regra de N D aplicada em p, temos uma contradi¸˜o. O que permite concluir que n˜o existe tal passo p. Fazemos ca a a demonstra¸˜o por casos, considerando cada uma das regras: ca Departamento de Ciˆncia de Computadores da FCUP — LC — Aula 6 e 2

1

φ1

.
.
.

.
.
.

n

φ→θ

.
.
.

.
.
.

φ2

→E

.
.
.

: φ φ→ψ ψ Seja θ a f´rmula deduzida no passo p o por aplica¸˜o de → E a φ → θ e φ. ca E sejam φ1, . . . , φk as premissas assumidas em θ , e, por hip´tese, θ n˜o o a
´ consequˆncia semˆntica delas. Mas e e a as premissas para φ → θ e φ est˜o a entre os φ1, . . . , φk e ambos s˜o cona sequˆncia semˆnticas delas: e a

Departamento de Ciˆncia de Computadores da FCUP — LC — Aula 6 e .
.
.

l

φ

.
.
.

.
.
.

φ3
.
.
.

.
.
.

p