LGEBRA Y MATEMTICA DISCRETA 1 LGICA PROPOSICIONAL
1.1. Definiciones bsicas
TEMA 1 1.2. Operaciones lgicas y tablas de verdad
1.3. Implicacin y equivalencia lgicas
1.4. Mtodos lgicos de demostracin
LGICA PROPOSICIONAL
1.1 DEFINICIONES BSICAS 1.1 DEFINICIONES BSICAS
Trmino
cada una de las partes que constituyen un Proposicin lgica
enunciado o discurso agrupacin de trminos de la que se puede
afirmar si su contenido es cierto o falso.
Trminos categoremticos
tienen significado propio e independiente
Trminos sincategoremticos
se utilizan para enlazar y modificar los
trminos categoremticos
1.1 DEFINICIONES BSICAS 1.1 DEFINICIONES BSICAS
Proposicin atmica
no se puede descomponer en partes que sean
a su vez proposiciones y est en afirmativo. Conectores proposicionales
trminos sincategoremticos que se utilizan
Proposicin molecular para modificar o enlazar proposiciones.
formada por una o ms proposiciones
atmicas modificadas o enlazadas por
trminos sincategoremticos.
1
1.1 DEFINICIONES BSICAS 1.1 DEFINICIONES BSICAS
Conectores Proposicionales Mondicos Conectores Proposicionales Didicos
se aplican a una sola proposicin se aplican a dos proposiciones
Negacin (no...) Conjuncin (...y...)
Disyuncin no exclusiva (...o...)
Disyuncin exclusiva (o...o...)
Condicional (si...entonces...)
Bicondicional (...si y slo si...)
1.1 DEFINICIONES BSICAS 1.1 DEFINICIONES BSICAS
Signo conectivo o constante lgica
Variable Proposicional smbolo que sustituye a un conector
smbolo que sustituye a una proposicin proposicional.
atmica.
negacin
conjuncin
disyuncin no exclusiva
disyuncin exclusiva
condicional o implicador
bicondicional o coimplicador
1.1 DEFINICIONES BSICAS 1.2 OPERACIONES LGICAS
Y TABLAS DE VERDAD
NEGACIN
Frmula lgica p p
Expresin simblica que sustituye a una
proposicin molecular
0 1
1 0
2
1.2 OPERACIONES LGICAS 1.2 OPERACIONES LGICAS
Y TABLAS DE VERDAD Y TABLAS DE VERDAD
CONJUNCIN DISYUNCIN NO EXCLUSIVA
p q pq p q pq
0 0 0 0 0 0
0 1 0 0 1 1
1 0 0 1 0 1
1 1 1 1 1 1
1.2 OPERACIONES LGICAS 1.2 OPERACIONES LGICAS
Y TABLAS DE VERDAD Y TABLAS DE VERDAD
DISYUNCIN EXCLUSIVA CONDICIONAL
p q pq p q pq
0 0 0 0 0 1
0 1 1 0 1 1
1 0 1 1 0 0
1 1 0 1 1 1
1.2 OPERACIONES LGICAS 1.3 IMPLICACIN Y EQUIVALENCIA LGICAS
Y TABLAS DE VERDAD
BICONDICIONAL
p q pq TAUTOLOGAS
0 0 1 PROPOSICIONES CONTRADICCIONES
0 1 0 PROPOSICIONES CONTINGENTES
1 0 0
1 1 1
3
1.3 IMPLICACIN Y EQUIVALENCIA LGICAS 1.3 IMPLICACIN Y EQUIVALENCIA LGICAS
SUFICIENCIA DE LA NEGACIN Y LA DISYUNCIN
EQUIVALENCIA LGICA
AB pq (pq)
AB es tautologa
pq pq
IMPLICACIN LGICA
AB
AB es tautologa pq (pq)(pq)
pq ((pq)(pq))
1.3 IMPLICACIN Y EQUIVALENCIA LGICAS 1.3 IMPLICACIN Y EQUIVALENCIA LGICAS
p q p q pq pq (pq) pq(pq)
0 0 1 1 0 1 0 1
0 1 1 0 0 1 0 1
1 0 0 1 0 1 0 1
1 1 0 0 1 0 1 1
1.3 IMPLICACIN Y EQUIVALENCIA LGICAS 1.4 MTODOS LGICOS DE DEMOSTRACIN
p q p pq pq pqpq
0 0 1 1 1 1
0 1 1 1 1 1
REGLAS BSICAS DE INFERENCIA
1 0 0 0 0 1
1 1 0 1 1 1
4
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
CONJUNCIN DISYUNCIN
INTRODUCCIN ELIMINACIN INTRODUCCIN ELIMINACIN
A AB AB A B AB
B A
C
AB A B AB AB B
C
C
producto simplificacin
adicin prueba por casos
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
NEGACIN CONDICIONAL
INTRODUCCIN ELIMINACIN
INTRODUCCIN ELIMINACIN
A AB
A A
B A
B B
AB B
A A
absurdo doble negacin
teorema de deduccin modus ponens
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
BICONDICIONAL
INTRODUCCIN ELIMINACIN
REGLAS DE INFERENCIA DERIVADAS
AB AB AB
BA
AB AB BA
5
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
SILOGISMO HIPOTTICO
MUTACIN DE PREMISAS
A (B C)
AB
BC
B (A C)
AC
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
CARGA DE PREMISAS
IDENTIDAD
A
A
A
B A
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
PROPIEDAD ASOCIATIVA
PROPIEDAD CONMUTATIVA
AB AB (A B) C (A B) C
BA BA A (B C) A (B C)
6
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
PROPIEDAD DISTRIBUTIVA
PROPIEDAD DE IDEMPOTENCIA
(A B) C (A B) C AA AA
(A C) (B C) (A C) (B C) A A
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
LEY DE ABSORCIN
CONTRAPOSICIN
AB
A (A B) A (A B)
BA
A A
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
INTRODUCCIN DE LA
MODUS TOLLENS DOBLE NEGACIN
AB A
B
A
A
7
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
PRINCIPIO DE NO
EX CONTRADICTIONE QUODLIBET
CONTRADICCIN
A A
(A A)
B
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
PRINCIPIO DEL TERCIO EXCLUSO
EXPORTACIN-IMPORTACIN DE
PREMISAS
AA
A (B C)
(A B) C
1.4 MTODOS LGICOS DE DEMOSTRACIN 1.4 MTODOS LGICOS DE DEMOSTRACIN
SILOGISMO DILEMAS
DISYUNTIVO
Constructivos Destructivos
AB AB
simple compuesto simple compuesto
A B
AB AB AB AB
B A AC AC CA CA
BC BD CB DB
C CD C CD
8
1.4 MTODOS LGICOS DE DEMOSTRACIN
LEYES DE DE MORGAN
(A B) (A B)
A B AB
