Marea

Fundamentos de Lógica Matemática Principia Matemática • • • • Conjunción (∧): Condicional (→): Bicondicional (↔): Disyuntiva exclusa (⊕): p∧q ≡ ¬(¬p∨¬q) p→q ≡ ¬p∨q p↔q ≡ ((p→q)∧(q→p)) ≡ [(¬p∨q)∧(¬q∨p)] p⊕q ≡ ¬(p↔q) Axiomas y reglas de PM 1. 2. 3. 4. (p∨p)→p q→(p∨q) (p∨q)→(q∨p) (p→q)→[(r∨p)→(r∨q)] Sistema inferencial del calculo de proposiciones: S→R ¬R__ ¬S Se representa: D((S→R)∧¬R, ¬S). C esuna conclusión lógica de P1, P2...: (P1∧P2∧...∧Pn)→C. (D[((S→R)∧¬R)→ ¬S]). O bien: (P1∧P2∧...∧Pn∧¬C) ((S→R)∧¬R∧S), es una contradicción. Sea ‘R’ la implicación directa o primitiva: S→T. Se llama contraria de ‘R’: ¬S→¬T. Recíproca de ‘R’: T→S. Contrarecíproca de ‘R’: ¬T→¬S. a) La implicación directa y su contrarrecíproca son equivalentes entre sí. b) La implicación contraria y su directa no sonequivalentes en general. La negación de la contraria tampoco es equivalente a la contraria. La negación de la contraria es equivalente a la directa. c) La implicación recíproca y su directa no son equivalentes. Tampoco la negación de la directa es equivalente a la recíproca. La negación de la recíproca es equivalente a la directa. d) La implicación contraria de la directa y la recíproca de la directason equivalentes entre sí, son mutuamente contrarrecíprocas una de otra. T→S : ‘S’ es necesaria para ‘T’; ‘T’ es suficiente para ‘S’. T↔S : ‘T’ es necesaria y suficiente para ‘S’; ‘S’ es necesaria y suficiente para ‘T’. Reglas de inferencia 1. Regla de separación (Sep.) o del modus ponens. Regla de eliminación del condicional (RE→): S→R S___ R 2. Regla de unión (Un.) o de introducción de laconjunción (RI ∧): S R___ S∧R

Lógica de proposiciones

1/15

Fundamentos de Lógica Matemática

3. Regla de inserción (Ins.): S→R R→T S→T 4. Regla de intercambio (Int.): S→R R↔T S→T Principio de resolución para la lógica de proposiciones: 1. Eliminar los condicionales y bicondicionales aplicando las definiciones de los mismos. 2. Introducir las negaciones aplicando las leyes de Morgan. 3. Pasara forma clausulada aplicando la ley distributiva para la disyunción. 4. Simplificar (Escribir solo una vez cláusulas idénticas, eliminar tautologías, escribir solo una vez si aparece el mismo literal varias veces en una cláusula). Tabla de verdad para conectivas p V V F F q V F V F      ¬p F F V V p∧q V F F F p∨q V V V F p⊕q F V V F p→q V F V V p↔q V F F V

Dos nuevas conectivas: (Deinterés en informática) NOR (↓) y NAND (|). (p↓q)≡¬(p∨q); (p|q)≡¬(p∧q). p V V F F q V F V F | | | | | p↓q V F F V p|q . V V V V Leyes de la lógica de proposiciones 1. Ley de identidad: p→p p↔p 2. Ley de la doble negación: p↔¬¬p 3. Ley del tercio excluso: p∨¬p

Lógica de proposiciones

2/15

Fundamentos de Lógica Matemática 4. Ley de contradicción: ¬(p∧¬p) 5. Leyes de Morgan: ¬(p∧q)↔(¬p∨¬q)¬(p∨q)↔(¬p∧¬q) 6. Leyes de reducción al absurdo: (¬p→(q∧¬q))↔p 7. Leyes de conmutación: (p∨q)↔(q∨p) (p∧q)↔(q∧p) (p↔q)↔(q↔p) 8. Leyes de asociación: ((p∨q)∨r)↔(p∨(q∨r)) ((p∧q)∧r)↔(p∧(q∧r)) ((p↔q)↔r)↔(p↔(q↔r)) 9. Leyes de transposición: (p→q)↔(¬q→¬p) (p↔q)↔(¬q↔¬p) 10. Leyes distributivas: (p∧(q∨r))↔((p∧q)∨(p∧r)) (p∨(q∧r))↔((p∨q)∧(p∨r)) (p→(q∧r))↔((p→q)∧(p→r)) (p→(q∨r))↔((p→q)∨(p→r)) 11. Leyes de permutación:(p→(q→r))↔(q→(p→r)) 12. Leyes del silogismo: (p→q)→((q→r)→(p→r)) 13. Silogismo hipotético o transitividad ((p→q)∧(q→r))→(p→r) ((p↔q)∧(q↔r))→(p↔r) 14. Leyes de inferencia de la alternativa o de los silogismos disyuntivos: [¬p∧(p∨q)]→q [p∧(¬p∨¬q)]→¬q 15. Ley del dilema constructivo: [(p∨q)∧(p→r)∧(q→r)]→r 16. Segunda ley del dilema constructivo: [(p→q)∧(r→s)∧(p∨r)]→(q∨s) 17. Ley del dilema destructivo:[(¬p∨¬q)∧(r→p)∧(s→p)]→(¬r∨¬s) 18. Ley de exportación: [(p∧q)→r]↔[(p→(q∨r)] 19. Ley de resolución: [(¬p∨q)∧(p∨r)]→(q∨r) 20. Ley del bicondicional: (p↔q)↔[(p→q)∧(q→p)] 21. Condicional-disyuncion: (p→q)↔(¬p∨q)

Lógica de proposiciones

3/15

Fundamentos de Lógica Matemática 22. Condicional-conjunción: (p→q)↔¬(p∧¬q) 23. Leyes de simplificación: (p∧q)→p p→(p∨q) 24. Leyes de expansión:...