p1-2011.2 - Gabarito

Prévia do material em texto

1) 
Alguns exemplos de cadeias ímpares: 
0, 1, 001, 110, 010, 101... 
Como pode ver, as cadeias ímpares são: 0 e 1. 
i) A base = {0, 1} 
ii) Para definir as funções geradoras, a gente tem que achar tais funções que 
aplicando a partir da base, todas as cadeias do conjunto são geradas. 
Logo, 
Existem quatro funções que geram todas as cadeias binárias: 
F(w) = 1w1 
G(w) = 0w0 
H(w) = 0w1 
I(w) = 1w0 
iii) O maior conjunto indutivo é o maior conjunto que obedeça aquelas regras, ou 
seja: que contenha a base {0, 1} e as funções f, g, h e i. O maior conjunto então é o 
conjunto de todas as cadeias binárias, porque é o maior conjunto que tenha tais 
regras. 
iv) Para um conjunto ser livremente gerado, ele precisa: 
a. Ter suas funções injetivas, ou seja, f(x) = f(y) se e somente se x = y. (tem que 
valer pra f, g, h e i). E acontece que sim, elas são injetivas, porque nossas 
funções são construtivas. 
b. As imagens de f, g, h e i precisam ser disjuntas. De fato, são: porque f, por 
exemplo, gera cadeias com as duas extremidades com “1”. E nenhuma outra 
gera. O mesmo argumento vale pra g,h e i. 
c. As funções não podem gerar a base. E elas não geram a base, porque elas são 
construtivas, ou seja, ao aplicar as funções, sempre geraremos objetos 
“maiores”. 
Então, sim, o conjunto é livremente gerado. 
 
2) 
Para provar algo por indução, precisamos primeiramente definir as funções que estão sendo 
pedidas no problema. Elas são: o número de sub-expressões e o número de conectivos 
(operadores). 
 
Seja S(x) o número de sub-expressões de x, e C(x) o número de conectivos de x: 
Para o caso atômico: 
S(x) = 1 
C(x) = 0 
Para o caso unário, onde x = ¬p (e p é uma fórmula qualquer) 
S(¬p) = 1 + S(p) 
C(¬p) = 1 + S(p) 
Para o caso binário, onde x = p#q, onde p e q são fórmulas quaisquer e # é um operador unário 
S(p#q) = 1 + S(p) + S(q) - |S(p)∩ S(q)| 
C(p#q) = 1 + C(p) + C(q) 
Pronto, definimos as funções. 
 
Agora precisamos definir nossas hipóteses de indução pro caso unário e binário: 
H.I pro unário: S(p) <= 2.C(p) + 1 
H.I 1 pro binário: S(p) <= 2.C(p) + 1 
H.I 2 pro binário: S(q) <= 2.C(q) + 1 
 
Agora, como último passo, iremos provas pros três casos: 
Caso atômico (base): 
S(p) <= 2.C(p) +1 
Sendo que S(p) = 1 e C(p) = 0, pro Atômico logo: 
1 <= 2.0 +1 [provado pela definição] 
 
Caso Unário: 
S(¬p) <= 2.C(¬p) +1 
Por definição, temos: 
1 + S(p) <= 2.( 1 + C(p) ) + 1 
1+ S(p) <= 2 + 2.C(p) + 1 
S(p) <= 2.C(p) + 1 + 1 
Como, por hipótese temos que S(p) <= 2.C(p) + 1, então, se adicionarmos +1 ao termo da 
direita, ainda continuará sendo verdade. 
Então, provamos por H.I. 
 
Caso binário: 
S(p#q) <= 2.C(p#q) + 1 
Por definição: 
1 + S(p) + S(q) - |S(p)∩ S(q)| <= 2. (1 + C(p) + C(q) ) + 1 
S(p) + S(q) - |S(p)∩ S(q)| <= 2 + 2.C(p) + 2.C(q) 
S(p) + S(q) - |S(p)∩ S(q)| <= 2.C(p) + 1 + 2.C(q) + 1 
Como, por hipótese S(p)<= 2.C(p) + 1 e S(q) <= 2.C(q) + 1, então: 
S(p) + S(q) <= 2.C(p) + 1 + 2.C(q) + 1 também é verdade. 
Porém 
|S(p)∩ S(q)| é sempre positivo, então, podemos subtrair algo positivo do termo menor, que 
ainda continuará sendo menor, então: 
S(p) + S(q) - |S(p)∩ S(q)| <= 2.C(p) + 1 + 2.C(q) + 1 
Está provado por H.I. 
 
3) seja T = {a1, a2, a3...} (premissas), e C = C1 (conclusão). 
Queremos demonstrar que 
 (T unido a C é inconsistente) é equivalente a (C é conclusão lógica de T) 
Vamos lá: 
¬C é conclusão lógica de T pode ser escrito assim: 
(T -> ¬C) = 1 
(¬T ou ¬C) = 1 [tirando o implica] 
(¬a1 v ¬a2 v ... v ¬an ) v ¬C = 1 [trocando T pelas premissas] 
(¬a1 v ¬a2 v ... v ¬an v ¬C ) = 1 [passando o C para dentro] 
¬(a1 ^ a2 ^ ... ^ an ^ C) = 1 [usando deMorgan “voltando”] 
¬¬( a1 ^ a2 ^ ... ^ an ^ C) = 0 [negando ambos os lados] 
( T ^ C )= 0 [trocando as premissas por T] 
T ^ C = 0 que dizer : T unido a C é inconsistente. Então, está demonstrado. Como se trata de 
um se e somente se, precisa ser demostrado a volta, que é só partir de baixo pra cima. 
 
4) i) pra resolver por resolução, você precisa: 
 Deixas todas as fórmulas na F.N.C (fórmula normal conjuntiva), ou seja: todas as 
negações devem estar juntas a um átomo (a uma letra, e não a um parêntese), todos os “e”s 
(^) devem estar fora dos parênteses e todos os “ou”s devem estar dentro dos parênteses. 
((p ou q) ^ r) está na F.N.C 
((p^q) ou r) não está na F.N.C 
(¬( p ou q) ^ r) ) não esta na F.N.C 
Após isto, você precisa negar a conclusão. 
Negada a conclusão, você vai operando entre as fórmulas com o intuito de achar o “falso” 
(absurdo), da seguinte forma: 
P ou Q 
¬P 
_____ 
Q 
Você acha o absurdo quando chega em algo do tipo P e ¬P. 
ii) na 4.2, o símbolo presente quer dizer “não é conseqüência lógica”. 
5) 
 
Existem duas redundâncias. Você deve identificar quais tipos são, e então normalizá-las. 
6) i) O teorema da extensão homomórfica única diz: 
 Se você tem um conjunto A que é indutivo (ou seja, contém a base e funções 
geradoras) e uma função que leva a base de A pra elementos do conjunto B, então existe uma 
função que leva o conjunto A todo pra B, e esta função é única. 
 A maior vantagem pra lógica proposicional é que, dado uma valoração pros átomos de 
uma fórmula, só existe uma forma de valorar a fórmula toda, ou seja, não existe uma fórmula 
“X” que seja verdade ou falsa ao mesmo tempo, por exemplo. 
ii) Ele precisa ser correto, ou seja, todas as fórmulas que são dadas como resposta (saída do 
sistema), são válidas [ou seja, o sistema é confiável].