amd1

1

TEMA 1

LÓGICA PROPOSICIONAL

ÁLGEBRA Y MATEMÁTICA DISCRETA 1 LÓGICA PROPOSICIONAL

1.1. Definiciones básicas1.2. Operaciones lógicas y tablas de verdad1.3. Implicación y equivalencia lógicas1.4. Métodos lógicos de demostración

Términocada una de las partes que constituyen un enunciado o discurso

Términos categoremáticostienen significado propio e independiente

Términos sincategoremáticosse utilizan para enlazar y modificar los términos categoremáticos

1.1 DEFINICIONES BÁSICAS

Proposición lógicaagrupación de términos de la que se puede afirmar si su contenido es cierto o falso.


Proposición atómicano se puede descomponer en partes que sean a su vez proposiciones y está en afirmativo.

Proposición molecularformada por una o más proposiciones atómicas modificadas o enlazadas por términos sincategoremáticos.


Conectores proposicionalestérminos sincategoremáticos que se utilizan para modificar o enlazar proposiciones.


2

Conectores Proposicionales Monádicosse aplican a una sola proposición

Negación (no...)


Conectores Proposicionales Diádicosse aplican a dos proposiciones

Conjunción (...y...)Disyunción no exclusiva (...o...)Disyunción exclusiva (o...o...)Condicional (si...entonces...)Bicondicional (...si y sólo si...)


Variable Proposicionalsímbolo que sustituye a una proposición atómica.


Signo conectivo o constante lógicasímbolo que sustituye a un conector proposicional.

negación ¬conjunción ∧disyunción no exclusiva ∨disyunción exclusiva ∆condicional o implicador →bicondicional o coimplicador ↔


Fórmula lógicaExpresión simbólica que sustituye a una proposición molecular


NEGACIÓN

p ¬p

0 11 0

OPERACIONES LÓGICAS Y TABLAS DE VERDAD

1.2

3

CONJUNCIÓN

p q p ∧ q

0 0 00 1 01 0 01 1 1


1.2

DISYUNCIÓN NO EXCLUSIVA

p q p ∨ q

0 0 00 1 11 0 11 1 1


1.2

DISYUNCIÓN EXCLUSIVA

p q p ∆ q

0 0 00 1 11 0 11 1 0


1.2

CONDICIONAL

p q p → q

0 0 10 1 11 0 01 1 1


1.2

BICONDICIONAL

p q p ↔ q

0 0 10 1 01 0 01 1 1


1.2

TAUTOLOGÍAS

PROPOSICIONES CONTRADICCIONES

PROPOSICIONES CONTINGENTES

1.3 IMPLICACIÓN Y EQUIVALENCIA LÓGICAS

4

EQUIVALENCIA LÓGICAA⇔B A↔B es tautología

IMPLICACIÓN LÓGICAA⇒ B A→B es tautología


SUFICIENCIA DE LA NEGACIÓN Y LA DISYUNCIÓN

p∧ q ⇔ ¬ (¬p∨ ¬q)

p→q ⇔ ¬p∨ q

p∆q ⇔ ¬ (¬p∨ q)∨ ¬ (p∨ ¬q)

p↔q ⇔ ¬ (¬ (¬p∨ q)∨ ¬ (p∨ ¬q))


p q ¬p ¬q p∧ q ¬p∨ ¬q0 0 1 1 0 1 0 1 1 0 0 11 0 0 1 0 11 1 0 0 1 0


¬ (¬p∨ ¬q) p∧ q↔¬ (¬p∨ ¬q) 0 1 0 1 0 1 1 1


p q ¬p p→q ¬p∨ q p→q↔¬p∨ q0 0 1 1 1 10 1 1 1 1 11 0 0 0 0 11 1 0 1 1 1


REGLAS BÁSICAS DE INFERENCIA

1.4 MÉTODOS LÓGICOS DE DEMOSTRACIÓN

5

INTRODUCCIÓN ELIMINACIÓN

A A ∧ B A ∧ BB

A ∧ B A B

producto simplificación

CONJUNCIÓN



A B A ∨ BAC

A ∨ B A ∨ B BC

C

adición prueba por casos

DISYUNCIÓN


NEGACIÓN


A ¬ ¬ A B ∧ ¬B

¬ A A

absurdo doble negación



A A → B B A

A → B B

teorema de deducción modus ponens


CONDICIONAL


A → B A ↔ B A ↔ B

B → A

A ↔ B A → B B → A


BICONDICIONAL

REGLAS DE INFERENCIA DERIVADAS


6

SILOGISMO HIPOTÉTICO

A → BB → C

A → C


MUTACIÓN DE PREMISAS

A → (B →C)

B → (A →C)


IDENTIDAD

A

A


CARGA DE PREMISAS

A

B→ A


PROPIEDAD CONMUTATIVA

A ∨ B A ∧ B B ∨ A B ∧ A


PROPIEDAD ASOCIATIVA

(A ∨ B) ∨ C (A ∧ B) ∧ C

A ∨ (B ∨ C) A ∧ (B ∧ C)


7

PROPIEDAD DISTRIBUTIVA

(A ∧ B) ∨ C (A ∨ B) ∧ C

(A ∨ C) ∧ (B ∨ C) (A ∧ C) ∨ (B ∧ C)


PROPIEDAD DE IDEMPOTENCIA

A ∧ A A ∨ A

A A


LEY DE ABSORCIÓN

A ∧ (A ∨ B) A ∨ (A ∧ B)

A A


CONTRAPOSICIÓN

A → B ¬ B → ¬ A


MODUS TOLLENS

A → B¬ B ¬ A


INTRODUCCIÓN DE LADOBLE NEGACIÓN

A

¬ ¬ A


8

EX CONTRADICTIONE QUODLIBET

A ∧ ¬ A

B


PRINCIPIO DE NO CONTRADICCIÓN

¬ (A ∧ ¬ A)


PRINCIPIO DEL TERCIO EXCLUSO

A ∨ ¬ A


EXPORTACIÓN-IMPORTACIÓN DE PREMISAS

A → (B → C)

(A ∧ B) → C


SILOGISMO DISYUNTIVO

A ∨ B A ∨ B

¬ A ¬ B

B A


DILEMAS

A ∨ B A ∨ B A → C A → CB → C B → D

C C ∨ D

¬ A ∨ ¬ B ¬ A ∨ ¬ B C → A C → AC → B D → B

¬ C ¬ C ∨ ¬ D

Constructivos Destructivos

simple compuesto simple compuesto


9

LEYES DE DE MORGAN

¬ (A ∨ B) ¬ (A ∧ B)

¬ A ∧ ¬ B ¬ A ∨ ¬ B


amd1

Business