Logica

Introducci´n a la L´gica Matem´tica o o a (Resumen Cap´ ıtulo I: C´lculo Proposicional) a
1.1 Definici´n. El Lenguaje del C´lculo Proposicional est´ compuesto de los siguientes eleo a a mentos: Letras sentenciales (o variables proposicionales): letras que representan afirmaciones (ser´n a usadas letras may´sculas A, B, C . . .). u Conectivos l´gicos: ¬ (negaci´n), o o ⇔ (equivalencia).
∨(disyunci´n), o

∧

(conjunci´n), ⇒ (implicaci´n) y o o

Las f´rmulas se definen recursivamente as´ o ı: 1. F´rmulas at´micas: toda letra sentencial es una f´rmula. o o o 2. F´rmulas complejas: si A y B son f´rmulas entonces ¬A, (A o o (A ⇔ B) son f´rmulas. o
∨

B), (A

∧

B), (A ⇒ B) y

1.1.

Sem´ntica: Tablas de Verdad a
A V V F F B V F V F A
∨

B

A V F

¬A F V

V V V FA V V F F

B V F V F

A

∧

B

V F F F

A V V F F

B V F V F

A⇒B V F V V

A V V F F

B V F V F

A⇔B V F F V

Observaci´n (conectivos adecuados): un conjunto de conectivos es llamado adecuado si los o otros conectivos pueden ser definidos en t´rminos de ellos. Por ejemplo {¬, ∨ } es un conjunto e adecuado de conectivos adecuado, pues los otros conectivos pueden ser definidosa partir de estos conectivos as´ ı: B ⇒ C es ¬B ∨ C, B ∧ C es ¬(¬B ∨ ¬C), B ⇔ C es (B ⇒ C) ∧ (C ⇒ B). 1.3 Definici´n. Una f´rmula B se llama tautolog´ si su tabla de verdad toma el valor V bajo o o ıa cualquier asignaci´n de verdad a sus variables proposicionales, se llama contradicci´n si su tabla o o de verdad toma el valor F bajo cualquier asignaci´n de verdad a sus variables proposicionales y ose llama contingencia si existen asignaciones de verdad V y F para la f´rmula. o 1.5 Proposici´n (Leyes del C´lculo Proposicional). Las siguientes son tautolog´ del c´lculo o a ıas a proposicional: (a) A
∨

¬A (Tercer Exclu´ ıdo).

(e) ¬¬A ⇔ A (Doble negaci´n). o (f ) (A ⇒ B) ⇔ (¬A (g) (A
∧ ∨ ∨

(b) A ⇒ A (Identidad). (c) (A (d) (A
∨ ∧

B). ¬B).
∧

A) ⇔ A (Idempotencia). A) ⇔ A(Idempotencia). 1

B) ⇔ ¬(¬A

(h) (A ⇔ B) ⇔ [(A ⇒ B)

(B ⇒ A)].

Leyes Conmutativas (i) (A (j) (A
∨ ∧

Leyes para ⇒ (p) (A ⇒ B) ⇔ (¬B ⇒ ¬A) (Contrarrec´ ıproco). (q) (A ⇒ (B ⇒ C)) ⇔ ((A de Hip´tesis). o
∨ ∧ ∧

B) ⇔ (B B) ⇔ (B

∨ ∧

A). A).

Leyes Asociativas (k) (A (l) (A
∨ ∧

B) ⇒ C) (Ley

(B (B

∨ ∧

C)) ⇔ ((A C)) ⇔ ((A

B) B)

∨ ∧

C). C).

(r) (A ⇒ (B ⇒ C)) ⇔(B ⇒ (A ⇒ C)) (Conmutatividad de Hip´tesis). o (s) ¬(A ⇒ B) ⇔ (A
∧

Leyes Distributivas (m) ((A (n) ((A
∧ ∨

¬B) (Negaci´n). o

(B (B

∨ ∧

C)) ⇔ ((A C)) ⇔ ((A

∧ ∨

B) B)

∨ ∧

(A (A

∧ ∨

C)). C)).

Leyes para ⇔ (t) (A ⇔ B) ⇔ (B ⇔ A) (Conmutativa). (u) (A ⇔ (B ⇔ C)) ⇔ ((A ⇔ B) ⇔ C) (Asociativa). (v) ¬(A ⇔ B) ⇔ (¬A ⇔ B) (Negaci´n). o

Leyes de D’ Morgan (o) ¬(A (p) ¬(A∨ ∧

B) ⇔ (¬A B) ⇔ (¬A

∧ ∨

¬B). ¬B).

M´todo para determinar si una f´rmula A es tautolog´ e o ıa: 1. Asignar F a A.1 2. Realizar los siguientes pasos hasta asigar ambos valores de verdad a una subf´rmula de A o o hasta asignar valores de verdad a todas las subf´rmulas de A (en todas las opciones que o se generen en el proceso). a) Asignar valores de verdad deducibles de las tablas deverdad de los conectivos l´gicos. o b) Si no hay valores de verdad deducibles y hay subf´rmulas sin valor de verdad, escoger o una subf´rmula B que no tenga asignado valor de verdad y crear dos copias (opciones) o de lo que va del proceso, asignando a B el valor V en una de las copias y el valor F en la otra. 3. Si en todas las opciones se obtienen contradicciones (f´rmulas con ambos valores devero dad), la f´rmula A es una tautolog´ en caso contrario A no es tautolog´ o ıa, ıa.

1.2. Sintaxis: Teor´ L ıa
2.1 Definici´n (Teor´ L). Sistema axiom´tico para la L´gica Proposicional Cl´sica: o ıa a o a (1) Lenguaje: como especificado en la Definici´n 1.1. Se consideran ¬ y ∨ como conectio vos primarios, y se definen los otros conectivos como especificado en la observaci´n sobre o conectivos...