Lista de exerccios #1
Lgica para cincia da computao
Conectivos proposicionais: ~ Smbolo de implicao semntica: Smbolo
de equivalncia semntica: Funo interpretao: IContradomnio de I: { V,
F }
Conveno: na elaborao da tabela verdade, usar { V, F }, nessa
ordem. NO USAR { 0, 1 } NEM { T, F }
1 - Qual o comprimento das frmulas abaixo?a) P Qb) ~ ( P Q ) ( R
S)c) ( ~ P ~ Q) ~ ( P Q ) d) ( A ( B ( C D ) ) ) ( ~ A ( ~ B ( C D
) ) )
2 - Indique o conjunto de subfrmulas das frmulas da questo
anterior.
3 - Dentre as concatenaes de smbolos a seguir, quais so frmulas
bem formadas e quais no so?
a) P trueb) P ( ( Q R ) ( ( P R ) ( P R ) ) )c) ( ( P ~ P ) ~ P
) Qd) ( P Q ) ( ( Q ~ P ) ~ ~ R ) e) ~ ~ Pf) Qg) ( P Q ) ( Q R )h)
P ~ Q
4 - O que se pode concluir:a') sobre I ( P Q ) se I ( P ) = V?
R: I ( P Q ) = Vb') sobre I ( P Q ) se I ( P ) = F? R: Nada se pode
concluir.c') sobre I ( P Q ) se I ( Q ) = V? R: Nada se pode
concluir.d') sobre I ( P Q ) se I ( Q ) = F? R: I ( P Q ) = Fe')
sobre I ( P Q ) se I ( P ) = V? R: Nada se pode concluir.f') sobre
I ( P Q ) se I ( P ) = V? R: Nada se pode concluir.
a) sobre I ( P Q ) se I ( P ) = Vb) sobre I ( P Q ) se I ( P ) =
Fc) sobre I ( P Q ) se I ( Q ) = Vd) sobre I ( P Q ) se I ( Q ) =
Fe) sobre I ( P Q ) se I ( P ) = Ff) sobre I ( P Q ) se I ( Q ) =
Vg) sobre I ( P Q ) se I ( P ) = Vh) sobre I ( P Q ) se I ( Q ) =
F
5 - Seja I uma interpretao tal que I ( P Q ) = V. O que se pode
concluir: a) sobre I ( ~ P Q )b) sobre I ( P ~ Q )c) sobre I ( P Q
)d) sobre I ( ( P R ) ( Q R ) ) e) sobre I ( ( P R ) ( Q R ) )
6 - Responda o exerccio anterior considerando que I ( P Q ) =
F.
7 - Mostre se os conjuntos de frmulas a seguir so satisfatveis
ou insatisfatveis:a) { (P Q), (P Q) } b) { (P Q), (P Q) }c) { (P
Q), (P Q) }d) { (P Q), (P ~ Q) }
8 - Sejam H e G as frmulas indicadas a seguir. Identifique,
justificando sua resposta, os casos em que H implica G.
a) H = P Q, G = P.b) H = P Q, G = P.c) H = P ~ Q, G = false.d) H
= false, G = P.e) H = P, G = true.
9 - Demonstre (sem pular nenhum passo) ou d um contra-exemploa)
H satisfatvel ~H satisfatvelb) H no satisfatvel H contraditriac) H
satisfatvel H no contraditriad) H contraditria ~H tautologiae) H no
tautologia H contraditriaf) H tautologia ~H contraditriag) H
tautologia H satisfatvelh) H implica G ( H G ) tautologiai) H
equivale a G ( H G ) tautologia
10 - Demonstre se as frmulas a seguir so tautologias usando o
mtodo da tabela verdade e o da rvore semntica.
a) H = ( P Q ) ( ~P Q )b) H = ~ ( P Q ) ( ~P Q )c) H = ( ~ P ~ Q
) ~ ( P ~ Q )d) H = ( P ~ Q ) ( ~ P ~ Q )
11 - Demonstre, sem pular nenhum passo, usando as regras de
interpretao de frmulas.a) I ( P Q ) = F I ( ~ P Q ) = Fb) I ( P Q )
= V I ( ~ P Q ) = Vc) I ( P Q ) = V I ~ ( P ~ Q ) = Vd) I ( ~ P ~ Q
) = V I (~ ( ~ P Q )) = V
