Sin título - Universidad Nacional de San Luis

´
´
LOGICA
PARA COMPUTACION
1. {(p ∧ q), (¬p ∧ q)}
A˜no 2014
´
´
PRACTICO
3: CALCULO
PROPOSICIONAL
2. {(p ∧ q), (¬p ∨ q)}
3. {(p → q), (p ∨ q), ¬q}
´
LA CONSECUENCIA LOGICA
4. {(p → q), (q → r), (r → s), (p → s)}
Ejercicio 1:
Investigar la validez de las siguientes argumentaciones utilizando tablas de verdad:
5. {(p → q), (q → r), (r → s), (p ∧ ¬s)}
1. {(p1 → p2 ), (p1 ∨ p2 } |= p2
6. {(p ∨ q), (p ∨ (q ∧ r)), (p → ¬r)}
2. {(p1 ∨ p2 ), (p1 → p3 ), (p2 → p3 )} |= p3
7. {(p → q), ((p ∧ q) → r), (q → ¬p)}
3. {((p ∨ q) → ¬p), (q → ¬p), (r → ¬p)} |= ¬p
4. {(p → (q ∨ r)), (r → s), (¬q ∨ s)} |= ¬(p ∧ ¬s)
Ejercicio 2:
Determinar, mediante tablas de verdad, si los siguientes argumentos son l´ogicamente correctos. Represente cada oraci´on como una f´ormula y verifique si la conclusi´on es l´ogicamente implicada por las suposiciones (utilice las mismas letras de proposici´on cuando estas proposiciones sean id´enticas):
1. Cuando tanto la temperatura como la presi´on atmosf´erica permanecen contantes,no llueve. La temperatura permanece constante. En consecuencia, en caso de que llueva, la presi´on atmosf´erica no
permanece constante.
2. Siempre que un n´umero x es divisible por 10, acaba en 0. El n´umero x no acaba en 0. Luego, x no es
divisible por 10.
3. X ser´a contratado si pasa todas las entrevistas. Si X tiene experiencia previa y no participa activamente en las reuniones, ser´a contratado. X tiene experiencia previa. Adem´as, X pasar´a todas las
entrevistas si participa activamente en las reuniones. Entonces X ser´a contratado.
4. Si Mar´ıa Lujan es espa˜nola, entonces Mar´ıa Lujan no es americana. Mar´ıa Lujan no es americana. Por
tanto, Mar´ıa Lujan es espa˜nola.
Ejercicio 3:
Dadas las siguientes f´ormulas del c´alculo proposicional, decidir, usando las tablas de verdad, si son o no
satisfacibles, justificando en cada caso su respuesta:
Ejercicio 5:
Utilizando a´ rboles de refutaci´on, demostrar si alguna de las f´ormulas del ejercicio 3 es una contingencia.
Para aqu´ellas que lo sean, hallar una valuaci´on que las satisfaga y otra que no las satisfaga, s´olo usando la
informaci´on provista por los a´ rboles.
Ejercicio 6:
Utilizando a´ rboles de refutaci´on, demostrar cu´ales de los conjuntos del ejercicio 4 son satisfacibles. Para
aqu´ellos que lo sean, hallar una valuaci´on que satisfaga a todas las f´ormulas, s´olo usando la informaci´on
provista por los a´ rboles.
Ejercicio 7:
Utilizando el m´etodo de los a´ rboles de refutaci´on, decidir si las siguientes f´ormulas son tautolog´ıas,
contradicciones o contingencias, justificando en cada caso su respuesta.
1. (¬(p1 ∨ p2 ) → ((p3 ∧ p1 ) ∨ (p2 → p3 )))
2. ¬((p1 → p3 ) → ((p2 → p3 ) → ((p1 ∨ p2 ) → p3 )))
3. (((p1 → p2 ) → p1 ) → p1 )
4. (¬(p1 ∨ p1 ) → (¬p1 ∨ ¬p1 ))
5. (((p1 ∧ p3 ) ∨ (¬p1 ∧ p2 )) → ¬p2 )
6. ((¬¬¬(p1 ∧ p2 ) ∨ p3 ) → p4 )
7. ((p1 ∨ ¬p1 ) ∨ (p2 ∧ ¬p2 ))
1. ((p1 → (p8 → p1 )) → ¬(p6 ∨ ¬p1 ))
Ejercicio 8:
2. ((q → (p ∧ ¬p)) → r)
a) Reescribir cada una de las siguientes inferencias utilizando la notaci´on habitual para expresar consecuencias l´ogicas.
3. ((p1 → (p1 ∧ p2 )) ∨ ((p3 ∧ ¬p3 ) ∨ (p5 → p6 )))
b) Usar el m´etodo de los a´ rboles de refutaci´on para determinar si alguna de las inferencias es v´alida.
Ejercicio 4:
Determinar, usando las tablas de verdad. si cada uno de los siguientes conjuntos de f´ormulas es o no
satisfacible. Justifique su respuesta. Para aqu´ellos que lo sean, dar una valuaci´on v que los satisfaga.
C´alculo Proposicional: La consecuencia l´ogica
Universidad Nacional de San Luis
1
1.
P
(P ∨ Q)
C´alculo Proposicional: La consecuencia l´ogica
Universidad Nacional de San Luis
2
2.
3.
4.
5.
6.
7.
8.
9.
10.
(P → Q)
P
Q
(P → Q)
¬P
¬Q
(P ∨ Q)
(P → Q)
Q
(P → Q)
(P → R)
(P → (Q ∧ R))
(P → (Q → R))
(P ∧ R)
R
(Q → S)
(¬S → ¬Q)
(P → Q)
(Q → R)
(P → R)
(P ∨ Q)
(P → R)
(Q → S)
(R ∨ S)
(P ∨ Q)
¬Q
P
C´alculo Proposicional: La consecuencia l´ogica
Universidad Nacional de San Luis
3