1 1.1 1.1 1.1 1.1 ÁLGEBRA Y MATEMÁTICA DISCRETA
TEMA 1 LÓGICA PROPOSICIONAL DEFINICIONES BÁSICAS
Término cada una de las partes que constituyen un
enunciado o discurso Términos categoremáticos
tienen significado propio e independiente Términos
sincategoremáticos se utilizan para enlazar y modificar
los términos categoremáticos DEFINICIONES
BÁSICAS Proposición atómica no se puede
descomponer en partes que sean a su vez proposiciones y
está en afirmativo. Proposición molecular
LÓGICA PROPOSICIONAL 1.1. Definiciones básicas 1.2.
Operaciones lógicas y tablas de verdad 1.3.
Implicación y equivalencia lógicas 1.4.
Métodos lógicos de demostración DEFINICIONES
BÁSICAS Proposición lógica agrupación
de términos de la que se puede afirmar si su contenido es
cierto o falso. DEFINICIONES BÁSICAS Conectores
proposicionales términos sincategoremáticos que se
utilizan para modificar o enlazar proposiciones. formada por una
o más proposiciones atómicas modificadas o
enlazadas por términos sincategoremáticos. 1
1.1 1.1 1.1 1.1 ? ? ? ? ? 1.1 1.2 DEFINICIONES BÁSICAS
Conectores Proposicionales Monádicos se aplican a una sola
proposición DEFINICIONES BÁSICAS Conectores
Proposicionales Diádicos se aplican a dos proposiciones
Negación (no…) Conjunción Disyunción no
exclusiva Disyunción exclusiva Condicional Bicondicional
(…y…) (…o…) (o…o…) (si…entonces…) (…si y
sólo si…) DEFINICIONES BÁSICAS Variable
Proposicional símbolo que sustituye a una
proposición atómica. DEFINICIONES BÁSICAS
Signo conectivo o constante lógica símbolo que
sustituye a un conector proposicional. negación
conjunción disyunción no exclusiva
disyunción exclusiva condicional o implicador
bicondicional o coimplicador ¬ DEFINICIONES BÁSICAS
OPERACIONES LÓGICAS Y TABLAS DE VERDAD NEGACIÓN
Fórmula lógica Expresión simbólica
que sustituye a una proposición molecular p 0 1 ¬p 1 0
2
1.2 1.2 1.2 1.2 1.2 1.3 OPERACIONES LÓGICAS Y TABLAS DE
VERDAD CONJUNCIÓN OPERACIONES LÓGICAS Y TABLAS DE
VERDAD DISYUNCIÓN NO EXCLUSIVA p 0 0 1 1 q 0 1 0 1 p ? q 0
0 0 1 p 0 0 1 1 q 0 1 0 1 p ? q 0 1 1 1 OPERACIONES
LÓGICAS Y TABLAS DE VERDAD DISYUNCIÓN EXCLUSIVA
OPERACIONES LÓGICAS Y TABLAS DE VERDAD CONDICIONAL p 0 0 1
1 q 0 1 0 1 p ? q 0 1 1 0 p 0 0 1 1 q 0 1 0 1 p ? q 1 1 0 1
OPERACIONES LÓGICAS Y TABLAS DE VERDAD BICONDICIONAL
IMPLICACIÓN Y EQUIVALENCIA LÓGICAS p q p ? q
TAUTOLOGÍAS 0 0 1 1 0 1 0 1 1 0 0 1 PROPOSICIONES
CONTRADICCIONES PROPOSICIONES CONTINGENTES 3
1.3 1.3 ? 1.3 1.3 p 0 0 1 1 q 0 1 0 1 1.3 1.4 IMPLICACIÓN
Y EQUIVALENCIA LÓGICAS EQUIVALENCIA LÓGICA A?B
IMPLICACIÓN Y EQUIVALENCIA LÓGICAS SUFICIENCIA DE
LA NEGACIÓN Y LA DISYUNCIÓN p?q ?
¬(¬p?¬q) A?B es tautología IMPLICACIÓN
LÓGICA A?B A?B es tautología p?q p?q p?q ? ?
¬p?q ¬(¬p?q)?¬(p?¬q)
¬(¬(¬p?q)?¬(p?¬q)) IMPLICACIÓN Y
EQUIVALENCIA LÓGICAS IMPLICACIÓN Y EQUIVALENCIA
LÓGICAS ¬p ¬q p?q ¬p?¬q 1 1 0 1 1 0 0 1 0
1 0 1 0 0 1 0 ¬(¬p?¬q) 0 0 0 1
p?q?¬(¬p?¬q) 1 1 1 1 IMPLICACIÓN Y
EQUIVALENCIA LÓGICAS MÉTODOS LÓGICOS DE
DEMOSTRACIÓN p q ¬p p?q ¬p?q p?q?¬p?q 0 0 1 1
0 1 0 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 1 REGLAS BÁSICAS DE
INFERENCIA 4
1.4 1.4 1.4 1.4 1.4 1.4 MÉTODOS LÓGICOS DE
DEMOSTRACIÓN CONJUNCIÓN MÉTODOS
LÓGICOS DE DEMOSTRACIÓN DISYUNCIÓN
INTRODUCCIÓN ELIMINACIÓN INTRODUCCIÓN
ELIMINACIÓN A A ? B A ? B A B A ? B B A A ? B A B A ? B A
? B C B C C producto simplificación adición prueba
por casos MÉTODOS LÓGICOS DE DEMOSTRACIÓN
NEGACIÓN MÉTODOS LÓGICOS DE
DEMOSTRACIÓN CONDICIONAL INTRODUCCIÓN A B ? ¬B
¬ A absurdo ELIMINACIÓN ¬¬ A A doble
negación INTRODUCCIÓN A B A ? B teorema de
deducción ELIMINACIÓN A ? B A B modus ponens
MÉTODOS LÓGICOS DE DEMOSTRACIÓN
BICONDICIONAL MÉTODOS LÓGICOS DE
DEMOSTRACIÓN INTRODUCCIÓN ELIMINACIÓN A ? B
A ? B A ? B REGLAS DE INFERENCIA DERIVADAS B ? A A ? B A ? B B ?
A 5
1.4 1.4 1.4 1.4 1.4 1.4 MÉTODOS LÓGICOS DE
DEMOSTRACIÓN SILOGISMO HIPOTÉTICO A ? B B ? C A ? C
MÉTODOS LÓGICOS DE DEMOSTRACIÓN IDENTIDAD A
A MÉTODOS LÓGICOS DE DEMOSTRACIÓN
MÉTODOS LÓGICOS DE DEMOSTRACIÓN
MUTACIÓN DE PREMISAS A ? (B ?C) B ? (A ?C) MÉTODOS
LÓGICOS DE DEMOSTRACIÓN CARGA DE PREMISAS A B? A
MÉTODOS LÓGICOS DE DEMOSTRACIÓN PROPIEDAD
ASOCIATIVA PROPIEDAD CONMUTATIVA A ? B B ? A A ? B B ? A (A ? B)
? C A ? (B ? C) (A ? B) ? C A ? (B ? C) 6
1.4 1.4 A A 1.4 1.4 1.4 1.4 MÉTODOS LÓGICOS DE
DEMOSTRACIÓN MÉTODOS LÓGICOS DE
DEMOSTRACIÓN PROPIEDAD DISTRIBUTIVA PROPIEDAD DE
IDEMPOTENCIA (A ? B) ? C (A ? C) ? (B ? C) (A ? B) ? C (A ? C) ?
(B ? C) A ? A A ? A MÉTODOS LÓGICOS DE
DEMOSTRACIÓN LEY DE ABSORCIÓN MÉTODOS
LÓGICOS DE DEMOSTRACIÓN CONTRAPOSICIÓN A ?
(A ? B) A A ? (A ? B) A A ? B ¬ B ?¬ A MÉTODOS
LÓGICOS DE DEMOSTRACIÓN MODUS TOLLENS A ? B ¬ B
¬ A MÉTODOS LÓGICOS DE DEMOSTRACIÓN
INTRODUCCIÓN DE LA DOBLE NEGACIÓN A ¬¬ A
7
1.4 1.4 1.4 1.4 1.4 1.4 MÉTODOS LÓGICOS DE
DEMOSTRACIÓN EX CONTRADICTIONE QUODLIBET A ?¬ A B
MÉTODOS LÓGICOS DE DEMOSTRACIÓN PRINCIPIO
DEL TERCIO EXCLUSO A ?¬ A MÉTODOS LÓGICOS DE
DEMOSTRACIÓN SILOGISMO DISYUNTIVO MÉTODOS
LÓGICOS DE DEMOSTRACIÓN PRINCIPIO DE NO
CONTRADICCIÓN ¬ (A ? ¬ A) MÉTODOS
LÓGICOS DE DEMOSTRACIÓN
EXPORTACIÓN–IMPORTACIÓN DE PREMISAS A ? (B ? C) (A
? B) ? C MÉTODOS LÓGICOS DE DEMOSTRACIÓN
DILEMAS Constructivos Destructivos A ? B ¬ A B A ? B ¬ B
A simple A ? B A ? C B ? C C compuesto A ? B A ? C B ? D C ? D
simple ¬ A ?¬ B C ? A C ? B ¬ C compuesto ¬ A
?¬ B C ? A D ? B ¬ C ?¬ D 8
1.4 MÉTODOS LÓGICOS DE DEMOSTRACIÓN LEYES DE
DE MORGAN ¬ (A ? B) ¬ A ?¬ B ¬ (A ? B) ¬ A
?¬ B 9