Deducción natural

Deducci´n Natural o
Jose Emilio Labra Gayo

Tabla de Contenidos
1. L´gica Proposicional o 2. L´gica de Predicados o 3. Referencias y Agradecimientos 2 5 9

1

´ 1 LOGICA PROPOSICIONAL

21.

L´gica Proposicional o

El m´todo de deducci´n natural, desarrollado por Gentzen, utiliza dos reglas e o de inferencia por cada conectiva: una para insertar la conectiva y otra paraeliminarla Las reglas de inferencia son: Cuadro 1: Reglas de Inferencia A B A∧B A∧B ∧E A∧B A B A B A∨B A→C B →C ∨E A∨B A∨B C A ... B A→B A→B B→A A↔B A ... B∧ ∼ B ∼A ∼A∨A T A∧ ∼ A F →E A→B B A↔B A→B A

∧I ∨I→I

↔I

↔E

A↔B B→A

∼I

∼E

TI FI

TE FE

∼A ... B∧ ∼ B A T ∼A∨A F A

A continuaci´n se incluyen varios ejemplos de demostraciones en deduci´n o o natural. Ejemplo 1 ([p∧q)⇒p∧(q∨r)]

Ejemplo 2 ([p→q,q→r) ⇒p→r]

´ 1 LOGICA PROPOSICIONAL

3

Ejemplo 3 ([p→q∨r,q→r,r→s) ⇒p→s]

Ejemplo 4 ([p→∼q,r→q) ⇒∼(p∧r)]

´ 1 LOGICA PROPOSICIONAL

4

Ejemplo 5 ([∼p) ⇒p→q]Ejemplo 6 (p↔∼∼p)

´ 2 LOGICA DE PREDICADOS

5

Ejemplo 7 (p→q⇒∼p∨q)

2.

L´gica de Predicados o

Para la l´gica de predicados se a˜aden las siguientes reglas de inferencia para o ninsertar y eliminar cada uno de los cuantificadores.

´ 2 LOGICA DE PREDICADOS

6

Cuadro 2: Reglas de Inferencia l´gica de Predicados o ∀I (t)libre ... A(t) ∀xA(x) A(t) ∃xA(x) ∀E ∀xA(x) A(t) ∃xA(x) ∃I∃E

A(t)libre ... B B

Deben cumplirse las siguientes normas: En las reglas ∀I y ∃E, el t´rmino t no debe aparecer en ninguna caja e anterior abierta. En la regla ∃E la f´rmula B no puedecontener el t´rmino t o e A continuaci´n se incluyen varias demostraciones de razonamientos en l´gica o o de predicados mediante deducci´n natural o Ejemplo 8 ([∀x(p(x)→q(x)),∀x(r(x)→q(x)),∀x(p(x)∨r(x)))⇒∀xq(x)]

Ejemplo 9 ([∀x(p(x)→q(x),∃xp(x)) ⇒∃xq(x)]

´ 2 LOGICA DE PREDICADOS

7

Ejemplo 10 ([∃xp(x)) ⇒∼∀x∼p(x)]

Ejemplo 11 ([∼∀x∼p(x)) ⇒∃xp(x)]

´ 2 LOGICA DE PREDICADOS

8...