Logica proposicional

Vista previa del material en texto

Lógica Proposicional
Universidad Nacional de Ingenieŕıa
Los Profesores
2021-1
Proposición Lógica
Definición (Proposición Lógica)
Una proposición lógica es una expresión o enunciado que tiene la cualidad
de ser verdadero o bien falsa, pero no ambos a la vez.
Ejemplo
1 “El cielo es azul”
2 “Aprobaré el examen sustitutorio de calculo diferencia”
3 “Los perros ladran”
4 “2 +
√
3 es un número racional?
5 “a + b ∈ Q, la suma de dos números reales siempre es un racional?”
6 “!Viva la UNI¡”
7 “¿Qué hacemos aqúı?”
8 “2 divide a b”
Proposición Lógica
Denotaremos a una proposición por una letra minuscula p, q, r , s, t, ... para
simplificación de las propsiciones y determinar su valor de verdad.
Desde que una proposición lógica solo puede tomar el valor o verdadero o
falso, entonces estos posibles valores lo representaremos en una tabla,
p
V
F
llamada tabla de verdad.
Definición (Conectores logicos o enlaces)
Un conecto lógico es aquel que unen a una a dos proposiciones (simples),
para dar origen a una nueva proposición (compuesta).
En la lógica formal existen los siguientes conectores:
Proposición Lógica
Definición
Sea la proposisción p, definimos su negación, denotado por ∼ p, como la
proposición con los valores opuestos cuya tabla de verdad es,
p ∼ p
V F
F V
Ejemplo
p : 5 + 7 = 11
∼ p : 5 + 7 6= 11
q : x + 3y ≥ z
∼ q : x + 3y < z
r : Diciembre es mes de navidad
∼ r : Diciembre no es mes de navidad.
Proposición Lógica
Definición (La conjunción)
Sean p y q dos proposiciones definimos la conjunción de ellos, denotado
por p ∧ q, como la proposición “p y q” cuyo tabla de verdad es dado por:
p q p ∧ q
V V V
V F F
F V F
F F F
Ejemplo
Sean p :“El cielo está nublado en invierno” y
q : “Lloverá hoy con seguridad”.
Determine la conjunción entre ellos.
Proposición Lógica
Ejemplo
Un rey somete a un prisionero a la siguiente prueba: Lo enfrenta a dos puertas, de
los que el prisionero debe elgir una; y entrar en la habitación correspondiente.Se
informa al prisionero que en la habitación puede haber un tigre o un gato. Como
es natural, el prisionero debe elegir la puerta que le lleva al gato. Para ayudarle,
en cada puerta hay un letrero:
Puerta 1 : En esta habitación hay un gato y en la otra un tigre.
Puerta 2 : En una de estas habitaciones hay un gato y en una de estas habita-
ciones hay un tigre.
Sabiendo que uno de los carteles dice la verdad y el otro no, determine la puerta
que debe elegir el prisionero.
Proposición Lógica
Definición (La disyunción)
Sean p y q dos proposiciones se define a disyunción de ellos, denotada
por p ∨ q; como la proposición p o q cuya tabla de verdad es como sigue:
p q p ∨ q
V V V
V F V
F V V
F F F
Ejemplo
Sean p : ”Dos es par”, y q :”Dos es mayor que tres”.
Determine la disyunción entre ellos.
Proposición Lógica
Definición (La disyunción exclusiva)
Sean p, q dos proposiciones, se define la disyunción exclusiva de ellos, denotado
por: p Y q o p4q, como la proposición “O p o q” con tabla de verdad como
sigue:
p q p4 q
V V F
V F V
F V V
F F F
Ejemplo
Sean p = ”Malena está en la UNI” y q = “Malena está en su casa”’
Determine la disyunción exclusiva entre ellos.
Proposición Lógica
Notemos de la tabla que la disyunción exclusiva el valor es verdadero cuan-
do las proposiciones toman valores diferentes y es falso cuando los dos
toman el mismo valor, entonces mostrar faćılmente que podemos definirla
como
p4q = (p ∨ q)∧ ∼ (p ∧ q).
Definición (La condicional)
Sean p y q dos proposiciones, definimos la condicional de ellos denotado
por p(antecedente) → q(consecuente), como la proposición ”p entonces
q”.
p q p → q
V V V
V F F
F V V
F F V
Proposición lógica
Ejemplo
Sea p : No postergarón el examen de Matemática una semana,
q : Yo no me presento al examen de Matemática. Determine la condicional
de ellos.
p → q : No postergarán el examen de Matemática una semana, entonces no
me presento al examen.
Yo no me presento al examen de Matemática a menos que lo postergan una
semana.
Definición (Bicondicional)
Sean p y q dos proposiciones definimos la bicondicional de ellos, denotado por
p ↔ q, como la proposición p si y solo si q, cuya tabla de verdad es:
p q p ↔ q
V V V
V F F
F V F
F F V
Proposición Lógica
Ejemplo
Sean p :“a es par” y q : “a2 es par”. Determine la bicondicional entre ellas.’
Ejemplo
En una isla hay dos tipos de personas la de los veraces (los que siempre dicen la
verdad) y los de los mentirosos (que siempre mienten). Un turista se encuentra
con tres personas (A,B y C) de dicha isla y cada uno le dice una frase.
A dice “B y C son veraces si y solo si C es veraz”.
B dice “ Si A y C son veraces, entonces B y C son veraces y A mentiroso”.
C dice “ B es mentiroso si y solo si A o B es veraz”.
Determinar quienes son veraces y quienes mentirosos.
Proposición Lógica
Definición (Equivalencia)
Decimos que dos proposiciones compuestas p, q son equivalentes si
tienen la misma tabla de verdad y en este caso lo escribimos p ≡ q.
Ejemplo
Pruebe que p ↔ q ≡∼ (p4q).
p q p ↔ q ∼ (p4q)
V V V V F
V F F F V
F V F F V
F F V V F
Proposición Lógica
Ejemplo
Pruebe que:
1 ∼ (p ∧ q) ≡∼ p∨ ∼ q
2 ∼ (p ∨ q) ≡∼ p∧ ∼ q
Leyes de Morgan.
p q ∼ (p ∧ q) ∼ p ∨ ∼ q ∼ (p ∨ q) ∼ p ∧ ∼ q
V V F V F F F F V F F F
V F V F F V V F V F F V
F V V F V V F F V V F F
F F V F V V V V F V V V
Definición (Tautoloǵıa)
Una proposición compuesta es una tautologia cuando su tabla de verdad tiene
solo valores verdaderos sin importar cuales son sus valores de verdad de las
proposiciones simples.
Proposición Lógica
Ejemplo
Determinar si las proposiciones, (p → q)↔ (∼ q ∨ p),
[(q ∧ p)→∼ p]∧ ∼ q son una una tautoloǵıa.
p q (p → q) ↔ (∼ q ∨ p) [(q ∧ p) → ∼ p] ∧ ∼ q
V V V V V V F F F F
V F F F V F V F V V
F V V F F F V V F F
F F V V V F V V V V
Leyes del álgebra de proposiciones
Ley de Idempotencia
a1. p ∨ p ≡ p
b1. p ∧ p ≡ p
Ley conmutativa
a2. p ∨ q ≡ q ∨ p
b2. p ∧ q ≡ q ∧ p
Ley asociativa
a3. (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
b3. (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Ley distributiva
a4. p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
b4. p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Ley identidad
a5.1 p ∨ F ≡ p
a5.2 p ∨ (∼ p) ≡ V
b5.1 p ∧ V ≡ p
b5.2 p ∧ (∼ p) ≡ F
Ley asociativa
a3. (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
b3. (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Ley complementaria
a6 ∼ (∼ p) ≡ p
Ley contrapositiva
a7 p → q ≡ (∼ q)→ (∼ p) ≡ (∼
p ∨ q)
Ley de absorción
a8.1 p ∧ (p ∨ q) ≡ p
a8.2 ∼ p ∧ (p ∨ q) ≡∼ p ∧ q
b6.1 p ∨ (p ∧ q) ≡ p
b6.2 ∼ p ∨ (p ∧ q) ≡∼ p ∨ q
Leyes del álgebra de proposiciones
Ley de diferencia
a9 p4q ≡ (p∧ ∼ q) ∨ (q∧ ∼ p) ≡ (p ∨ q)∧ ∼ (p ∧ q)
Ejemplo
Simplifique la siguiente expresión:
[((∼ p) ∧ q)→ (r∧ ∼ r)]∧ ∼ q.
[((∼ p) ∧ q)→ (r∧ ∼ r)]∧ ∼ q ≡ [((∼ p) ∧ q)→ F ]∧ ∼ q
≡ [∼ ((∼ p) ∧ q) ∨ F ]∧ ∼ q
≡ (p∨ ∼ q)∧ ∼ q
≡ ∼ q
EJERCICIOS
Ejemplo
Determine si la proposición M → N es una tautoloǵıa, siendo
M ≡ {[p → (q∧ ∼ r)] ∧ [p ∧ (q → r)]} ∨ {[p ∧ q ∧ (p ∨ q)] ∨ [r ∧ (∼ r ∨ q) ∧ p]}
N ≡ {[(∼ q ∧ p) ∨ (∼ p ∧ q) ∨ (p → r)∧ ∼ (p ↔ q)]}4[q ∧ ((t ∧ s)→ q)]
M ≡ {[p →∼ (∼ q ∨ r)] ∧ [p ∧ (q → r)]} ∨ {[(p ∧ q)] ∨ [(r ∧ q) ∧ p]}
M ≡ {[p →∼ (∼ q ∨ r)] ∧ [p ∧ (q → r)]} ∨ {[(p ∧ q)] ∨ [(p ∧ q) ∧ r ]}
M ≡ {[∼ p∨ ∼ (q → r)] ∧ [p ∧ (q → r)]} ∨ {(p ∧ q)}
M ≡ {[∼ (p ∧ (q → r)] ∧ [p ∧ (q → r)]} ∨ {(p ∧ q)}
M ≡ F ∨ (p ∧ q) ≡ p ∧ q
N ≡ {[(∼ q ∧ p) ∨ (∼ p ∧ q) ∨ (p → r)∧ ∼ (p ↔ q)]}4[q ∧ ((t ∧ s)→ q)]
≡ {[(∼ q ∧ p) ∨ (∼ p ∧ q) ∨ ((∼ p) ∨ r)]∧ ∼ (p ↔ q)}4[q ∧ (∼ (t ∧ s) ∨ q)]
≡ {[(∼ q ∧ p) ∨ (∼ p) ∨ r ]∧ ∼ (p ↔ q)}4q
≡ {(∼ p∨ ∼ q ∨ r)∧ ∼ (p ↔ q)}4q
≡ {[∼ (p ∧ q) ∨ r)] ∧ [(p ∨ q)∧ ∼ (p ∧ q)]}4q
≡ {∼ (p ∧ q) ∧ (p ∨ q)}4q
≡ (p4q)4q ≡ p4(q4q) ≡ p4F ≡ p
Luego (p ∧ q)→ p ≡ (∼ p∨ ∼ q) ∨ p ≡ V∨ ∼ q ≡ V
EJERCICIOS
Ejemplo
Si m y n son proposiciones, se define la operación ∗ como m ∗ n =∼ m ∧ n y además
m ≡ [(p∧ ∼ q)∨ ∼ (p ∧ q)]↔∼ (p ∨ q) y
n ≡ [p ↔ (q∨ ∼ r)] ∧ [p → (q∧ ∼ r)] ∧ [p ∧ (q → r)]
m ≡ [(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 ∨ q) ∨ (p ∧ q)
≡ ∼ ((p ∨ q)∧ ∼ (p ∧ q) ≡ p ↔ q
Si se sabe que q y r no tienen el mismo valor de verdad. Sea q ≡∼ r
n ≡ [p ↔ (q∨ ∼ r)] ∧ [p → (q∧ ∼ r)] ∧ [p ∧ (q → r)]
≡ [p ↔ (q ∨ q)] ∧ [p → (q ∧ q)] ∧ [p ∧ (q →∼ q)]
≡ [p ↔ q] ∧ [p → q] ∧ [p ∧ (∼ q∨ ∼ q)]
≡ (p → q) ∧ (q → p) ∧ (p → q) ∧ (p∧ ∼ q)
≡ (p → q) ∧ (q → p) ∧ (p∧ ∼ q)
≡ (p ∼ ∨q) ∧ (∼ q ∨ p) ∧ (p∧ ∼ q) ≡ (∼ p ∧ q)∧ ∼ q ≡ F
∴ m ∗ n ≡∼ (p ↔ q) ∧ F ≡ F ∧ F ≡ F .
EJERCICIOS
Ejemplo
Simplifica [(∼ q →∼ p)→ (∼ p →∼ q)]∧ ∼ (p ∧ q)
[(∼ q →∼ p)→ (∼ p →∼ q)]∧ ∼ (p ∧ q) ≡ [(p → q)→ (q → p)]∧ ∼ (p ∧ q)
≡ [(p → q)→ (q → p)] ∧ (p →∼ q)
≡ [∼ (p → q) ∨ (q → p)] ∧ (∼ p∨ ∼ q)
≡ [(p∧ ∼ q) ∨ (∼ q ∨ p)] ∧ (∼ p∨ ∼ q)
≡ [∼ q ∨ p] ∧ (∼ p∨ ∼ q)
≡ ∼ q ∨ (p∧ ∼ p)
≡ ∼ q
EJERCICIOS
Ejemplo
Halle el valor de verdad de M = A ∨ B, donde:
A = [p → (q∧ ∼ r)] ∧ [p ∧ (q → r)]
B = [(p ∧ q) ∧ (p ∨ q)] ∨ [r ∧ (∼ r ∨ q) ∧ p]
A ≡ [p → (q∧ ∼ r)]∧ ∼ [p →∼ (q → r)]
≡ [p → (q∧ ∼ r)]∧ ∼ [p → (q∧ ∼ r)]
≡ F
B ≡ [p ∧ q] ∨ [(r ∧ q) ∧ p]
≡ p ∧ (q ∨ (r ∧ q))
≡ p ∧ q
Por lo tanto M = F ∨ (p ∨ q) ≡ p ∧ q
EJERCICIOS
Ejemplo
Simplifique N = C4D, si:
C = [((∼ q ∧ p) ∨ (∼ p ∧ q)) ∨ (p → r)]∧ ∼ (p ↔ q)
D = q ∧ ((t ∧ s)→ q)
C ≡ [((∼ q ∧ p) ∨ (∼ p ∧ q)) ∨ (∼ p ∨ r)] ∧ (p4q)
≡ [(∼ q ∧ p) ∨ (∼ p) ∨ r ] ∧ ((p ∨ q)∧ ∼ (p ∧ q))
≡ [∼ (p ∧ q) ∨ r ]∧ ∼ (p ∧ q) ∧ (p ∨ q)
≡ ∼ (p ∧ q) ∧ (p ∨ q)
≡ p4q
D ≡ q ∧ ((t ∧ s)→ q)
≡ q ∧ (∼ (t ∧ s) ∨ q)
D ≡ q.
N ≡ C4D ≡ (p4q)4q ≡ p4(q4q) ≡ p
EJERCICIOS
Ejemplo
Determinar si es una tautologia:
{[(p → q) ∨ (q ∧ r)]∨ ∼ [(q → r) ∧ (p ∨ (p ∧ m))]}∨ ∼ [(p → q) ∧ (r →∼ p)]
{[(p → q) ∨ (q ∧ r)]∨ ∼ [(q → r) ∧ (p ∨ (p ∧ m))]}∨ ∼ [(p → q) ∧ (r →∼ p)]
{[(∼ p ∨ q) ∨ (q ∧ r)]∨ ∼ [(∼ q ∨ r) ∧ p]}∨ ∼ [(∼ p ∨ q) ∧ (∼ r∨ ∼ p)]
{[∼ p(∨q ∨ (q ∧ r))]∨ ∼ [(∼ q ∨ r) ∧ p]}∨ ∼ [(∼ p ∨ q) ∧ (∼ r∨ ∼ p)]
{(∼ p ∨ q) ∨ [(q∧ ∼ r) ∨ (∼ p)]} ∨ [(p∧ ∼ q) ∨ (r ∧ p)]
{((∼ p) ∨ (∼ p)) ∨ [q ∨ (q∧ ∼ r)]} ∨ [(p∧ ∼ q) ∨ (r ∧ p)]
(∼ p) ∨ q ∨ (p∧ ∼ q) ∨ (r ∧ p)
q ∨ (r ∧ p) ∨ (∼ p) ∨ (p∧ ∼ q)
q ∨ (r ∧ p) ∨ (∼ p∨ ∼ q)
(q∨ ∼ q) ∨ [(r ∧ p) ∨ (∼ p)]
V ∨ (r∨ ∼ p) ≡ V