Universidade Tecnológica Federal do Paraná
Departamento Acadêmico de Informática
Disciplina: Lógica Para Computação (IF61B)
Prof. Adolfo Neto – 1a Verificação de Aprendizagem
Data: 23/04/2010 Alun*: _____________________________________________________
Em caso de dúvida sobre o enunciado das questões, pergunte ao professor.
1) Desenhe um mapa mental sobre o sistema KE. Seu mapa mental deverá ter pelo menos 10
nós/células. E deverá ter um nó central.
2) Desenhe a árvore de análise da seguinte fórmula:
((p¬¬¬s)((ppq))¬q))
3) Simplifique a fórmula da questão 2, removendo todos os parênteses desnecessários.
4) Adicione parênteses à fórmula abaixo para que ela fique de acordo com as regras de formação de
fórmulas da lógica clássica proposicional vistas em (SILVA; FINGER; MELO, 2006):
¬sq¬¬¬sp¬¬qp
5) Escreva o conjunto de sub-fórmulas próprias da fórmula da questão 4. E calcule a complexidade
da fórmula da questão 2.
6) Escreva uma fórmula que seja logicamente equivalente à fórmula da questão 4 e cuja
complexidade seja menor em pelo menos 7 unidades.
7) Se for possível, dê uma valoração que satisfaça a fórmula da questão 2, colorindo (ou marcando
com V e F) a árvore de análise desenhada na questão 2. Caso não seja possível, dê uma valoração
que falsifique a fórmula.
8) Provar ou refutar a seguinte afirmação, usando Tabelas da Verdade.
p¬¬¬q(¬¬pr) 
rpq
onde “” é o símbolo que estamos usando para representar conseqüência lógica.
2
3
9) Considerar a assinatura ∑=[R ,R ,C,V,F¹,F²], em que:
• R²={S, T, >, <, >=, <=, =}
• R3={RT}
• C={adolfont, KentBeck, martinfowler, 50,100, 5000}
• V={x,y,z}
• F¹={seguidores, seguidos}
• F²={seguidores-em-comum}
Identificar, dentre as sequencias de símbolos a seguir, quais pertencem ao conjunto de fórmulas
bem formadas da lógica de predicados definidos pela assinatura ∑ (isto é, quais pertencem a F(∑)):
a) xy(seguidores(x)>>seguidos(y))
b) RT(adolfont,KentBeck,100) ¬RT(srlm,KentBeck,100)
c) x (seguidores(x)>50 seguidos(x)<100  seguidores-em-comum(x,z)=100)
d) xy(S(x,y)S(y,x)  t (TT(x,t)  RT(y,x,t)))
e) seguidores(adolfont)=seguidos(KentBeck)+5000
Obs.1: Para cada item responda “Pertence a F(∑)” ou “Não pertence a F(∑)”.
Obs.2: Os operadores de comparação “>”, “<”, etc. podem ser escritos de forma infixa. Isto é, em
vez de escrever “>(t1,t2)”, escrevemos “t1>t2”, onde t1 e t2 são termos.
10) Suponha que temos os seguinte símbolos representando predicados: S(x,y) significa que “x
segue y”; T(x,t) significa que “x tuitou o tuíte t”; RT(x,y,t) significa que “o tuiteiro x retuitou o tuíte
t tuitado por y”. E que podemos usar as constantes adolfont, KentBeck, martinfowler e
DAINF_UTFPR. E que temos as variáveis x,y,z,t. Usando estas definições, represente as frases
abaixo como fórmulas da lógica de predicados:
a) Existiu um tuíte de KentBeck que adolfont retuitou.
b) Todos os usuários do Twitter retuitam todos os tuítes de KentBeck (exceto o próprio
KentBeck).
c) Não existe nenhum usuário que siga adolfont e não siga KentBeck.
d) Todos os usuários do Twitter que seguem adolfont e DAINF_UTFPR, também seguem
KentBeck e martinfowler.
11) Formular uma especificação formal (usando lógica de predicados e a notação complementar
apresentada pelo professor) para um programa P que recebe como entrada quatro números inteiros
distintos (em variáveis independentes) e retorna um vetor contendo os quatro números em ordem
crescente.
12) Prove ou refute (se for este o caso, mostre também a valoração contra-exemplo), usando tablôs
KE, o sequente abaixo
¬¬p2, p2(p2p1) , ¬(¬p4p1) ├ p4p1
Valores das questões:
Questões 11 e 12 valem 1,5 ponto.
Questões 1, 5, 6 e 10 valem 1 ponto.
Todas as demais valem 0,5 ponto.
Universidade Tecnológica Federal do Paraná
Departamento Acadêmico de Informática
Disciplina: Lógica Para Computação (IF61B)
Prof. Adolfo Neto – 1a Verificação de Aprendizagem
Data: 23/04/2010 Alun*: _____________________________________________________
Em caso de dúvida sobre o enunciado das questões, pergunte ao professor.
1) Desenhe um mapa mental sobre a semântica de valorações da lógica clássica proposicional. Seu
mapa mental deverá ter pelo menos 10 nós/células. E deverá ter um nó central.
2) Desenhe a árvore de análise da seguinte fórmula:
((((¬¬¬pq)p)¬q)(ps))
3) Simplifique a fórmula da questão 2, removendo todos os parênteses desnecessários.
4) Adicione parênteses à fórmula abaixo para que ela fique de acordo com as regras de formação de
fórmulas da lógica clássica proposicional vistas em (SILVA; FINGER; MELO, 2006):
¬sq¬¬sp¬¬qp
5) Escreva o conjunto de sub-fórmulas próprias da fórmula da questão 4. E calcule a complexidade
da fórmula da questão 2.
6) Escreva uma fórmula que seja logicamente equivalente à fórmula da questão 4 e cuja
complexidade seja menor em pelo menos 6 unidades.
7) Se for possível, dê uma valoração que satisfaça a fórmula da questão 2, colorindo (ou marcando
com V e F) a árvore de análise desenhada na questão 2. Caso não seja possível, dê uma valoração
que falsifique a fórmula.
8) Provar ou refutar a seguinte afirmação, usando Tabelas da Verdade.
rpq

p¬¬¬q(¬¬pr)
onde “” é o símbolo que estamos usando para representar conseqüência lógica.
2
3
9) Considerar a assinatura ∑=[R ,R ,C,V,F¹,F²], em que:
• R²={S, T, >, <, >=, <=, =}
• R3={RT}
• C={adolfont, KentBeck, martinfowler, 50,100, 5000}
• V={x,y,z,t}
• F¹={seguidores, seguidos}
• F²={seguidores-em-comum}
Identificar, dentre as sequencias de símbolos a seguir, quais pertencem ao conjunto de fórmulas
bem formadas da lógica de predicados definidos pela assinatura ∑ (isto é, quais pertencem a F(∑)):
a) xz (seguidores(x)>50 seguidos(x)<150  seguidores-em-comum(x,z)=100)
b) xy(S(x,y)S(y,x)  t (TT(x,t)  RT(y,x,t)))
c) xy(seguidores(x)>>seguidos(y))
d) RT(adolfont,KentBeck,100) ¬RT(martinfowler,KentBeck,100)
e) seguidores(adolfont)=seguidos(KentBeck)+50+100
Obs.1: Para cada item responda “Pertence a F(∑)” ou “Não pertence a F(∑)”.
Obs.2: Os operadores de comparação “>”, “<”, etc. podem ser escritos de forma infixa. Isto é, em
vez de escrever “>(t1,t2)”, escrevemos “t1>t2”, onde t1 e t2 são termos.
10) Suponha que temos os seguinte símbolos representando predicados: S(x,y) signifique que “x
segue y”; T(x,t) significa que “x tuitou o tuíte t”; RT(x,y,t) significa que “o tuiteiro x retuitou o tuíte
t tuitado por y”. E que podemos usar as constantes adolfont, KentBeck, martinfowler e
DAINF_UTFPR. E que temos as variáveis x,y,z,t. Usando estas definições, represente as frases
abaixo como fórmulas da lógica de predicados:
a) Existiu um tuíte de adolfont que martinfowler retuitou.
b) Todos os usuários do Twitter retuitam todos os tuítes de KentBeck (exceto martinfowler).
c) Não existe nenhum usuário que siga martinfowler e também siga KentBeck.
d) Todos os usuários do Twitter que seguem adolfont e DAINF_UTFPR, também seguem
KentBeck ou martinfowler.
11) Formular uma especificação formal (usando lógica de predicados e a notação complementar
apresentada pelo professor) para um programa P que recebe como entrada quatro números inteiros
distintos (em variáveis independentes) e retorna um vetor contendo os quatro números em ordem
descrescente.
12) Prove ou refute (se for este o caso, mostre também a valoração contra-exemplo), usando tablôs
KE, o sequente abaixo
p2(p2p3) , ¬(p2¬p1), ¬¬¬¬p2 ├ p3p1
Valores das questões:
Questões 11 e 12 valem 1,5 ponto.
Questões 1, 5, 6 e 10 valem 1 ponto.
Todas as demais valem 0,5 ponto.