A LÓGICA PARA COMPUTAÇÃO

UFPE-SISTEMAS DE INFORMAÇÃO

LÓGICA PARA COMPUTAÇÃO

LISTA 1

1) Construa uma árvore semântica para as formulas abaixo, verificando se as mesmas são válidas.  

[pic 1]

2) Utilizando o método da árvore semântica demonstre que a fórmula abaixo é válida:

a) (S → (¬C ˄ ¬Q)) ˄ ((¬C ˄ Q) → ¬S) 

 

b) (P ↔ R) → (¬P ∨ R) ∨ (¬R ∨ P)

3)Utilizando o método de indução verifique a seguinte fórmula abaixo:

[pic 2]

4) Utilizando o método da indução prove as seguintes fórmulas:

a) 1² + 2² + 3² +... + n² = (n/6)(n + 1)(2n + 1) , para todo n pertencente ao N

b) 1.2 + 2.3 + 3.4 +... + n(n + 1) = (n/3)(n + 1)(n + 2) , para todo n pertencente ao N

c) 1 + 3 + 5 +. . . + (2n − 1) = n 2 , n ≥ 1

d) 2n < 2n + 1, para todo n pertencente ao N

5) Considere G uma das fórmulas indicada a seguir.

a)¬PvQ

b) ¬Q->P

c)P <-> Q

d)P -> Q

e) ¬Q -> ¬P

f)P ^ ¬Q

Determine, utilizando o método da negação ou absurdo, os casos em que:

i)(P ^ Q) implica G

ii)(P -> Q) implica G

iii)(P v Q) implica G

iv)(P <-> Q) implica G

6) Demonstre, utilizando o método da negação ou absurdo, se as fórmulas a seguir são tautologias ou não. Justifique sua resposta

G= (¬P -> Q) -> ((¬Q -> P) ^ (P v Q))

H= (P -> (Q-> R)) -> (P^Q) -> R)

G=H <-> (H v G)

7) Considere as fórmulas a seguir e prove pelo método da negação ou absurdo se tais formulas são tautologias. Justifique sua resposta.

 

H= (¬ (P v ¬Q) v R) v (R -> (Q -> P))

E= (((P ^S) <-> P) <-> (P -> P1)) -> (((( P ^ Q) <-> P) ^(( P ^ R) <-> R) -> P)

G= (P v Q) v (¬P ^Q)

8) Sabendo que os valores lógicos das proposições p e q são respectivamente F e V, determinar o valor lógico da proposição:

(p ^ (~q  → p)) ^ ((p ↔ ~q) → q v ~p)