UTFPR/DAINF/ENG. COMPUTAÇÃO/LÓGICA
ALUNO:
PROF. CESAR AUGUSTO TACLA
24/4/2012 PARCIAL 1
INSTRUÇÕES :
1. deixe somente uma caneta, um lápis e uma borracha em cima da mesa;
2. deixe todo o restante do material ao lado da carteira, no chão;
3. deixe o(s) celular(es) e qualquer dispositivo eletrônico visível(eis) em cima do material que está no chão;
4. prova individual e SEM CONSULTA a qualquer material e individual ;
5. pode ser feita à lápis e entregue à lápis;
6. coloque o nome em todas as folhas;
7. em caso de dúvidas, anote a interpretação dada à questão na própria prova.
8. as provas podem ser diferentes em detalhes imperceptíveis a distância.
1.
[(1 pt) sintaxe LP] Dada a gramática no formato BNF (Baur-Naur Form) da Lógica Proposicional (LP) para
uma fórmula ∅, construa uma fórmula indicando passo-a-passo qual regra utilizou (p é a regra 1,
¬éa2, … . Esta fórmula deve ter complexidade/tamanho mínimo igual a 8.
∅ ∷= |¬| ∧ | ∨ | → Se preferir, ao invés da BNF, utilize os casos indutivos sendo que Llp significa linguagem lógica
proposicional (Silva et al., 2006) – indique b, para caso básico, 1, para caso indutivo 1, ….
2.
[(1,5 pt) sintaxe LP – árvore de análise e complexidade de fórmula]. Construa a árvore de análise para a fórmula
abaixo, dê todas as suas subfórmulas e reescreva a fórmula com parênteses.
∧ ∨ ¬ → 3.
[(1,5 pt) semântica da lógica proposicional – valoração, tabela verdade] Indique se as fórmulas abaixo são
satisfazíveis, insatisfazíveis ou válidas e justifique sua afirmação mostrando a valoração dos átomos para
cada uma delas.
a.
b.
4.
→ → ¬ ∨ → [(1 pt) semântica da LP – consequência lógica] Dado o conjunto de fórmulas Γ (ou teoria), responda se a fórmula
A é consequência lógica de Γ. Escreva formalmente o problema e demonstre sua resposta.
Γ = → , ¬
) = ¬
Pág. 1/2
UTFPR/DAINF/ENG. COMPUTAÇÃO/LÓGICA
ALUNO:
PROF. CESAR AUGUSTO TACLA
24/4/2012 PARCIAL 1
5.
[(1 pt) sintaxe da LPO – árvore de análise e variáveis livres] Seja φ a fórmula ∃+,+, - ∧ ∀-/- → ¬01, -
a. (0,5) desenhe a árvore de análise de φ
b. (0,3) identifique todas as folhas em φ que são variáveis livres ou presas
c. (0,2) modifique a fórmula, sem eliminar variáveis, para que não haja variáveis livres.
6.
[(4 pt) modelo da LPO] Suponha que queremos representar conhecimento acerca de relações familiares
tradicionais; suponha também que somente existem pessoas neste domínio do conhecimento – não há outros
tipos de objetos envolvidos.
a. (0,5) Defina funções que permitam representar:
i) uma pessoa tem um e somente um pai biológico;
ii) uma pessoa tem uma e somente uma mãe biológica.
b. (0,5) Defina predicados - e explique em linguagem natural o significado dos seus termos - que permitam
representar:
i) há pessoas;
ii) há homens;
iii) há mulheres;
iv) há casais;
v) uma pessoa é progenitora de outras pessoas;
vi) ume pessoa é mais velha do que outras;
c. (1,5) Defina sentenças quantificadas que permitam representar:
i) pessoas são necessariamente homens ou mulheres;
ii) se alguém é homem então não é mulher e vice-versa;
iii) a relação casais é simétrica, por exemplo, se João forma um casal com Maria então Maria forma um
casal com João;
iv) casais são formados por pessoas de sexos diferentes;
v) toda pessoa tem um pai biológico homem e uma mãe biológica mulher;
vi) há ao menos um casal formado por um homem e uma mulher, tal que o homem é mais velho do que
o pai da mulher.
d. (1,5) Construa um modelo que satisfaça todas as sentenças que construiu no item c:
i) defina um conjunto de objetos para o modelo;
ii) dê a interpretação dos símbolos de constantes;
iii) dê a interpretação dos símbolos de função;
iv) dê a interpretação dos símbolos de predicados;
v) dê o contexto que tornam as sentenças v e vi do item c verdadeiras.
Pág. 2/2