MP2 Gabarito

1. (0,25) Considere um alfabeto  ={ a,b,c, (,),+,*} Considere C o fecho indutivo sob X e F. Onde X ={ a,b,c } e F é o conjunto de funções geradoras ={ f 1,f2,f3 } definidas a seguir: f1: * *  * f1 (x,y) = x+y f2: * *  * f2 (x,y) = x*y f3: *  * f3 (x) = (x)
O Conjunto C é Livremente Gerado? Justifique, explicando se ele atende a cada uma das propriedades de um CLG, e dê um exemplo para cada propriedade.
Obs: Respostas sem justificativas não serão consideradas.
Resposta fornecida pela Prof Anjolina:
Não é Livremente Gerado, pois:
- Os conjuntos imagem de f1 e f2 não são disjuntos. Ex: Com f1 (a,b*c) = a+b*c e f2(a+b,c) = a+b*c
- Não gera elementos da base. Mas, continua não sendo um CLG por ter falhado na primeira propriedade.
- As funções são injetoras. Atende a essa propriedade, porém, como falhou na primeira acima citada, continua não sendo livremente gerado.

2. (0,25) (Provas por Indução)
Prove por indução que o número de nós de uma árvore sintática de ϕ é no máximo igual a quantidade de símbolos da expressão. Não esqueça de definir as funções recursivas e indique cada etapa da prova
Tese: n(ᶲ) ≤ t(ᶲ)
Tal que: n(ᶲ) = número de nós de ᶲ, e t(ᶲ) = número de símbolos de ᶲ.
Caso Base: ᶲ é atômico
● n(ᶲ) = 1
● t(ᶲ)
=1
1 ≤ 1, VERDADE!
Caso Unário: ᶲ = (¬ᶿ)
H.I : n(ᶿ) ≤ t(ᶿ)
● n((¬ᶿ)) = 1 + n(ᶿ)
● t((¬ᶿ)) = 3 + t(ᶿ)
1 + n(ᶿ) ≤ 3 + t(ᶿ)
1 + n(ᶿ) ≤ 3 + t(ᶿ) – Aritmética n(ᶿ) ≤ t(ᶿ) – HIPÓTESE DE INDUÇÃO
Caso Binário: ᶲ = (α □ β)
H.I1 : n(α) ≤ t(α)
H.I2 : n(β) ≤ t(β)
● n(α □ β) = 1 + n(α) + n(β)
●

t(α □ β) = 3 + t(α) + t(β)

1 + n(α) + n(β) ≤ 3 + t(α) + t(β)
1 + n(α) + n(β) ≤ 3 + t(α) + t(β) – Aritmética n(α) + n(β) ≤ t(α) + t(β) – HIPÓTESE DE INDUÇÃO n(β) ≤ t(β) – HIPÓTESE DE INDUÇÃO

3 (0,25) Prove a sentença abaixo pelo Método da Resolução, justiçando a resposta encontrada: {(Q v R) ^ ¬D ^ (¬C v D v ¬U) ^ (R->U) } |= (¬Q → ¬C)
Resposta:
Passando para a forma normal conjuntiva:
{QvR, ¬D, (¬C v D v ¬U), (¬RvU), ¬Q, C}
QvR
¬Q
______
R
¬R v U
________
U
¬C