miércoles, 12 de septiembre de 2012

Demostraciones lógicas

Obtuvimos de la página rinconmatematico.com (del foro de lógica y teoría de conjuntos), el siguiente ejercicio:


1. El lenguaje a utilizar consta del alfabeto de símbolos: ¬, →, (, ), p, q, etc.

2. Un conjunto de fórmulas bien formadas (fbf), que son aquellas que cumplen:

i. p, q, r, etc. son cada una fbf.

ii. Si A y B son fbf, así lo son ¬A y  ¬B.

iii. El conjunto de todas las fbf. es generado por (i) y (ii)

3. Axiomas. Para cada A, B, fbf  se cumple:

L1  (A → (B → A))
L2  ((A → (B → C) → ((A → B) → (A → C))
L3  (¬A → ¬B) → (B → A)

4. Regla de inferencia.
De A, A → B  es consecuencia inmediata B.

5. También pueden usarse las siguientes formas adicionales de deducción:
1. Si γ, A ⊢ B entonces γ ⊢ (A → B)
2. A → B, B → C ⊢ A → C

A) Demuéstrese:

A.1) (p → q) → ((¬p → ¬q) → (q → q)
A.2) ((p → (q → r)) → (p → q)) → ((p → (q → r)) → (p → r))
A.3) (p → (p → q)) → (p → q)
A.4)  p → (q → (p → q))

B) Como ejercicio adicional puede intentarse demostrar estas formas adicionales a partir de L1, L2, L3 y la regla de inferencia. 

No hay comentarios: