Álgebra Lógica Proposicional ]

Vista previa del material en texto

Lógica proposicional
Centro de Estudios Preuniversitarios CEPRE - UNI
Los Profesores c©
4 de marzo de 2017
1 / 24
Lógica proposicional
N
Contenido Teórico
¿Que es la lógica?
Es la ciencia que estudia los razonamientos.
2 / 24
Lógica proposicional
N
Contenido Teórico
Proposición Lógica
Definición
Es toda expresión del lenguaje que tiene la cualidad de ser ver-
dadero o falso, solo uno de ellos.
Ejemplos:
√
2 es irracional.
La Odisea fue escrita por Homero.
3 es un número par.
2 6= 6 .
Si Juan miente entonces Maŕıa dice la verdad.
3 / 24
Lógica proposicional
N
Contenido Teórico
Proposición Lógica
Definición
Es toda expresión del lenguaje que tiene la cualidad de ser ver-
dadero o falso, solo uno de ellos.
Ejemplos:
√
2 es irracional.
La Odisea fue escrita por Homero.
3 es un número par.
2 6= 6 .
Si Juan miente entonces Maŕıa dice la verdad.
3 / 24
Lógica proposicional
N
Contenido Teórico
Conectores Lógicos
Definición
Los conectores lógicos son términos de enlace entre proposicio-
nes, estos son:
Conector Nombre Lectura
∼ Negación no
∨ Disyunción o
∧ Conjunción y
−→ Condicional entonces
←→ Bicondicional si y sólo si
Observación:
p −→ q
{
p es condición suficiente para q
q es condición necesaria para p
4 / 24
Lógica proposicional
N
Contenido Teórico
Conectores Lógicos
Definición
Los conectores lógicos son términos de enlace entre proposicio-
nes, estos son:
Conector Nombre Lectura
∼ Negación no
∨ Disyunción o
∧ Conjunción y
−→ Condicional entonces
←→ Bicondicional si y sólo si
Observación:
p −→ q
{
p es condición suficiente para q
q es condición necesaria para p
4 / 24
Lógica proposicional
N
Contenido Teórico
Proposición simple y compuesta
Definición
Una proposición será llamada simple si no presenta conectores
lógicos en su estructura, caso contrario será llamada compuesta.
Ejemplo:
√
2 es irracional.
Lima es la capital de Perú y Quito de Ecuador.
Aprenderas matemática si y solo si tienes imaginación.
Cervantes escribio Romeo y Julieta.
Hoy es lunes si y sólo si mañana es martes.
SCCSC
5 / 24
Lógica proposicional
N
Contenido Teórico
Proposición simple y compuesta
Definición
Una proposición será llamada simple si no presenta conectores
lógicos en su estructura, caso contrario será llamada compuesta.
Ejemplo:
√
2 es irracional.
Lima es la capital de Perú y Quito de Ecuador.
Aprenderas matemática si y solo si tienes imaginación.
Cervantes escribio Romeo y Julieta.
Hoy es lunes si y sólo si mañana es martes.
SCCSC
5 / 24
Lógica proposicional
N
Contenido Teórico
Proposición simple y compuesta
Definición
Una proposición será llamada simple si no presenta conectores
lógicos en su estructura, caso contrario será llamada compuesta.
Ejemplo:
√
2 es irracional.
Lima es la capital de Perú y Quito de Ecuador.
Aprenderas matemática si y solo si tienes imaginación.
Cervantes escribio Romeo y Julieta.
Hoy es lunes si y sólo si mañana es martes.
SCCSC
5 / 24
Lógica proposicional
N
Contenido Teórico
Fórmula lógica
Definición
Variable proposicional.
Representan proposiciones, serán denotadas por letras
minúsculas p, q, r , s, t, etc.
Fórmula lógica.
Es una expresión que contiene un número finito de variables
proposicionales y conectores lógicos, en una correcta
combinación.
Ejemplo:
(p ∧ q)→ r
∼ (p ∨ q)↔ (∼ p)
(q ∧ p)∨ ∼ (∼ p∨ ∼ q)
6 / 24
Lógica proposicional
N
Contenido Teórico
Fórmula lógica
Definición
Variable proposicional.
Representan proposiciones, serán denotadas por letras
minúsculas p, q, r , s, t, etc.
Fórmula lógica.
Es una expresión que contiene un número finito de variables
proposicionales y conectores lógicos, en una correcta
combinación.
Ejemplo:
(p ∧ q)→ r
∼ (p ∨ q)↔ (∼ p)
(q ∧ p)∨ ∼ (∼ p∨ ∼ q)
6 / 24
Lógica proposicional
N
Contenido Teórico
Fórmula lógica
Definición
Variable proposicional.
Representan proposiciones, serán denotadas por letras
minúsculas p, q, r , s, t, etc.
Fórmula lógica.
Es una expresión que contiene un número finito de variables
proposicionales y conectores lógicos, en una correcta
combinación.
Ejemplo:
(p ∧ q)→ r
∼ (p ∨ q)↔ (∼ p)
(q ∧ p)∨ ∼ (∼ p∨ ∼ q)
6 / 24
Lógica proposicional
N
Contenido Teórico
Tabla de verdad
Tenemos las siguientes tablas
p ∼ p
V F
F V
p q p ∨ q p ∧ q p −→ q p ←→ q
V V V V V V
V F V F F F
F V V F V F
F F F F V V
7 / 24
Lógica proposicional
N
Contenido Teórico
Ejercicio 1
Determine la tabla de verdad de la fórmula lógica
((p −→ q)∧ ∼ q) −→ q
Solución:
p q ((p −→ q) ∧ ∼ q) −→ q
V V V F F V V
V F F F V V F
F V V F F V V
F F V V V F F
Observación: El número de entradas en la tabla de verdad es:
2número de variables
8 / 24
Lógica proposicional
N
Contenido Teórico
Ejercicio 1
Determine la tabla de verdad de la fórmula lógica
((p −→ q)∧ ∼ q) −→ q
Solución:
p q ((p −→ q) ∧ ∼ q) −→ q
V V V F F V V
V F F F V V F
F V V F F V V
F F V V V F F
Observación: El número de entradas en la tabla de verdad es:
2número de variables
8 / 24
Lógica proposicional
N
Contenido Teórico
Ejercicio 1
Determine la tabla de verdad de la fórmula lógica
((p −→ q)∧ ∼ q) −→ q
Solución:
p q ((p −→ q) ∧ ∼ q) −→ q
V V V F F V V
V F F F V V F
F V V F F V V
F F V V V F F
Observación: El número de entradas en la tabla de verdad es:
2número de variables
8 / 24
Lógica proposicional
N
Contenido Teórico
Ejercicio 2
Determine la tabla de verdad de la fórmula lógica
(r ∨ q) −→∼ (r −→ p)
p q r (r ∨ q) −→ ∼ (r −→ p)
V V V V F F V
V V F V F F V
V F V V F F V
V F F F V F V
F V V V V V F
F V F V F F V
F F V V V V F
F F F F V V V
9 / 24
Lógica proposicional
N
Contenido Teórico
Ejercicio 2
Determine la tabla de verdad de la fórmula lógica
(r ∨ q) −→∼ (r −→ p)
p q r (r ∨ q) −→ ∼ (r −→ p)
V V V V F F V
V V F V F F V
V F V V F F V
V F F F V F V
F V V V V V F
F V F V F F V
F F V V V V F
F F F F V V V
9 / 24
Lógica proposicional
N
Contenido Teórico
Ejercicio 3
Se tiene dos tarjetas rotuladas con los siguientes mensajes
Tarjerta 1: Las dos tarjetas son las ganadoras.
Tarjeta 2: La otra tarjeta es la ganadora.
Considere que si la tarjeta 1 es la ganadora, su mensaje es ver-
dadero, pero si no es la ganadora, su mensaje es falso y si la
tarjeta 2 no es la ganadora, su mensaje es verdadero, pero si es
la ganadora, su mensaje es falso. .
¿Hay tarjeta ganadora ?
10 / 24
Lógica proposicional
N
Contenido Teórico
Ejercicio 3
Solución:
Sean las proposiciones
1 p: Tarjeta 1 es la ganadora.
2 q: Tarjeta 2 es la ganadora.
p q p ∧ q p
V V V F
V F F F
F V F F
F F F V
Luego de la tabla
p ≡ F
q ≡ V
por lo tanto la tarjeta 2 es la ganadora.
11 / 24
Lógica proposicional
N
Contenido Teórico
Tautoloǵıa, Contradicción, Contin-
gencia.
Definición:
Una fórmula lógica se llama tautoloǵıa si siempre es VERDAD,
independiente de los valores de verdad de las variables
proposicionales.
Una fórmula lógica se llama contradicción si siempre es FALSA,
independiente de los valores de verdad de las variables
proposicionales.
Una fórmula lógica se llama contingencia si no es tautoloǵıa ni
contradición.
12 / 24
Lógica proposicional
N
Contenido Teórico
Tautoloǵıa, Contradicción, Contin-
gencia.
Definición:
Una fórmula lógica se llama tautoloǵıa si siempre es VERDAD,
independiente de los valores de verdad de las variables
proposicionales.
Una fórmula lógica se llama contradicción si siempre es FALSA,
independiente de los valores de verdad de las variables
proposicionales.
Una fórmula lógica se llama contingencia si no es tautoloǵıa ni
contradición.
12 / 24
Lógica proposicional
N
Contenido Teórico
Tautoloǵıa, Contradicción, Contin-
gencia.
Definición:
Una fórmula lógica se llama tautoloǵıa si siempre es VERDAD,
independiente de los valores de verdad de las variables
proposicionales.
Una fórmula lógica se llamacontradicción si siempre es FALSA,
independiente de los valores de verdad de las variables
proposicionales.
Una fórmula lógica se llama contingencia si no es tautoloǵıa ni
contradición.
12 / 24
Lógica proposicional
N
Contenido Teórico
Tautoloǵıa, Contradicción, Contin-
gencia.
Ejemplo:
tautoloǵıa contradicción
(p ∧ q) −→ p (p ∧ q)∧ ∼ p
p q (p ∧ q) −→ p
V V V
V F V
F V V
F F V
p q (p ∧ q)∧ ∼ p
V V F
V F F
F V F
F F F
13 / 24
Lógica proposicional
N
Contenido Teórico
Equivalencia lógica
Definición
Dos fórmulas lógicas α(p, q, · · · ) y β(p, q, · · · ) son equivalentes,
y se denotan por α(p, q, · · · ) ≡ β(p, q, · · · ), si tienen la misma
tabla de verdad.
Ejemplo:
Las fórmulas p −→ q y ∼ p ∨ q
p q p −→ q
V V V
V F F
F V V
F F V
p q ∼ p ∨ q
V V V
V F F
F V V
F F V
son equivalentes.
p −→ q ≡ ∼ p ∨ q
14 / 24
Lógica proposicional
N
Contenido Teórico
Equivalencia lógica
Definición
Dos fórmulas lógicas α(p, q, · · · ) y β(p, q, · · · ) son equivalentes,
y se denotan por α(p, q, · · · ) ≡ β(p, q, · · · ), si tienen la misma
tabla de verdad.
Ejemplo:
Las fórmulas p −→ q y ∼ p ∨ q
p q p −→ q
V V V
V F F
F V V
F F V
p q ∼ p ∨ q
V V V
V F F
F V V
F F V
son equivalentes.
p −→ q ≡ ∼ p ∨ q
14 / 24
Lógica proposicional
N
Contenido Teórico
Leyes Lógicas
Son equivalencias notables
Idempotencia
p ∨ p ≡ p
p ∧ p ≡ p
Conmutativa
p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p
Asociativa
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributiva
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
15 / 24
Lógica proposicional
N
Contenido Teórico
Leyes Lógicas
Morgan
∼ (p ∨ q) ≡∼ p ∧ ∼ q
∼ (p ∧ q) ≡∼ p ∨ ∼ q
Condicional
p → q ≡∼ p ∨ q
Bicondicional
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ (p ∧ q) ∨ (∼ p ∧ ∼ q)
Complemento
p ∨ ∼ p ≡ V
p ∧ ∼ p ≡ F
∼ (∼ p) ≡ p
16 / 24
Lógica proposicional
N
Contenido Teórico
Leyes Lógicas
Identidad
p ∨ V ≡ V
p ∨ F ≡ p
p ∧ V ≡ p
p ∧ F ≡ F
Absorción
p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p
p ∨ (∼ p ∧ q) ≡ p ∨ q
p ∧ (∼ p ∨ q) ≡ p ∧ q
17 / 24
Lógica proposicional
N
Contenido Teórico
Ejercicio 4
Simplifique
[(∼ p ∧ q) −→ (q −→ p)]∧ ∼ (∼ p ∧ q)
Solución:
Tenemos
[(∼ p ∧ q) −→ (q −→ p)] ∧ ∼ (∼ p ∧ q)
≡ [∼ (∼ p ∧ q) ∨ (q −→ p)] ∧ ∼ (∼ p ∧ q)
≡ [∼ (∼ p ∧ q) ∨ (q −→ p)] ∧ ∼ (∼ p ∧ q)
≡ ∼ (∼ p ∧ q)
≡ p ∨ ∼ q
18 / 24
Lógica proposicional
N
Contenido Teórico
Ejercicio 4
Simplifique
[(∼ p ∧ q) −→ (q −→ p)]∧ ∼ (∼ p ∧ q)
Solución:
Tenemos
[(∼ p ∧ q) −→ (q −→ p)] ∧ ∼ (∼ p ∧ q)
≡ [∼ (∼ p ∧ q) ∨ (q −→ p)] ∧ ∼ (∼ p ∧ q)
≡ [∼ (∼ p ∧ q) ∨ (q −→ p)] ∧ ∼ (∼ p ∧ q)
≡ ∼ (∼ p ∧ q)
≡ p ∨ ∼ q
18 / 24
Lógica proposicional
N
Contenido Teórico
Disyunción Excluyente
Definición
El conector disyunción excluyente 4, se define como
p q p4q
V V F
V F V
F V V
F F F
Tenemos las siguientes equivalencias:
p4q ≡∼ (p ←→ q)
p4q ≡ q4p
(p4q)4r ≡ p4(q4r)
p4F ≡ p
p4V ≡∼ p
p4p ≡ F
19 / 24
Lógica proposicional
N
Contenido Teórico
Ejericio 5
Simplifique:
(p4q)4[(p4q)4p]
Solución: Tenemos
(p4q) 4 [(p4q)4p]
≡ p4q 4 p4q4p
≡ p4q 4 p4q 4p
≡ p4p 4 q4q 4p
≡ F 4 F 4p
≡ F4F 4 p
≡ F 4 p
≡ p
20 / 24
Lógica proposicional
N
Contenido Teórico
Ejericio 5
Simplifique:
(p4q)4[(p4q)4p]
Solución: Tenemos
(p4q) 4 [(p4q)4p]
≡ p4q 4 p4q4p
≡ p4q 4 p4q 4p
≡ p4p 4 q4q 4p
≡ F 4 F 4p
≡ F4F 4 p
≡ F 4 p
≡ p
20 / 24
Lógica proposicional
N
Contenido Teórico
Seminario
Problema 1
Sean las proposiciones
p: Las estrellas irradian luz
q: Los cuerpos celestes reflejan la luz
r: Los cuerpos celestes giran.
Representar simbólicamente:
”Si no es cierto que las estrellas irradian luz y que los
cuerpos celestes reflejan la luz, entonces estos no giran”
21 / 24
Lógica proposicional
N
Contenido Teórico
Seminario
Problema 5
Simplifique
(p ∧ (q −→∼ p)) ∧ [(p ∧ (p −→ q)) −→ r ] ∧ r
22 / 24
Lógica proposicional
N
Contenido Teórico
Seminario
Problema 9
Dadas las proposiciones lógicas p, q, r , s; tal que p −→ (q4r) es
falso, indique el valor de verdad de las siguientes proposiciones
1 (q ←→ r) −→ p
2 p −→ (q4 ∼ r)
3 p4(s ←→∼ s)
23 / 24
Lógica proposicional
N
Contenido Teórico
Seminario
Problema 18
Se define p ∗ q = (p∧ ∼ q) ∨ (q∨ ∼ p), simplique la expresión
[(∼ p ∗ q) −→ q]←→ [p −→ (q ∗ p)]
24 / 24
Lógica proposicional
N
	Contenido Teórico