Exercícios Resolvidos - Estruturas Lógicas e Homomorfismos

ESTRUTURAS E HOMOMORFISMOS 1 15 Defina uma Lestrutura a estrutura e uma lassinatura associada e transcreva as seguintes sentenças para a lógica de primeira ordem a A soma de dois números primos não é nem primo nem par b Se dois números tem divisor comum distinto de 1 então pelo menos um deles não é primo E DomínioE é o conjunto dos naturais DetaqueE a com a E 1 FunçõesE soma divcom com soma E xy xy divcom E xy mdcxy RelaçõesE Primo Par com Primo E x x é primo e Par E x x é par a VxVy PrimoxPrimoy ParsomaxyPrimosomaxy b VxVy divcomxy 1 PrimoxvPrimoy 2 15 Considere as Lestruturas A e B definidas a seguir e verifique se o mapeamento h N N hx 3 x é um homomorfismo de A para B A DomA são os números naturais DestaquesA Funçõs A f f A xy x y RelaçõesA B DomB são os números naturais DestaquesB Funçõs B f f B xy x y RelaçõesB hf A xy f B hxhy 3 fAxy f B 3 x 3 y 3 xy 3 x 3 y 3 xy 3 xy Por vacuidade as demais condições são satisfeitas SINTAXE DA LÓGICA DE PREDICADOS 3 15 Verifique se os seguintes conjuntos de termos são unificáveis apresentando um unificador mais geral caso sejam ou explicando todos os motivos porque não são unificáveis caso não sejam a hxfxz hgyfgbz S hxfxz hgyfgbz DDT S x gy fx fgb z z DDT S x gy x gb z z EET S x gy x gb SDV by S x gb Unificador mais geral gby b gxfxx gfyffzz S gxfxx gfyffzz DDT S x fy fx ffz x z DDT S x fy x fz x z Não é possível uma substituição pois a mesma variável recebe três termos distintos dois dos quais são uma variável e uma função aplicada à mesma variável 4 10 Dê a forma padrão de skolem da seguinte fórmula da lógica de predicados xyDgxVOfy yMgy SEMÂNTICA DA LÓGICA DE PREDICADOS 5 15 Considere as Lestruturas C e D definidas a seguir e escreva uma sentença na lógica de primeira ordem para a qual C seja modelo e D seja contramodelo Lembrando que não é necessário usar todos os símbolos C Domínio são os números naturais um destaque a com a C 0 uma função unária f com f C x x1 uma relação binária R com R C xy x é maior que y D Domínio são os números reais um destaque a com a D 0 uma função unária f com f D x x1 uma relação binária R com R D xy x é maior que y VxyEzRxzRzy Esta afirmação é verdadeira para números reais e falsa para os naturais 6 15 Considere a Lestrutura C definida na questão anterior e defina o seu diagrama positivo Seja b C 1 e C uma extensão de C contendo b como destaque fa b ffa fb fffa ffb Mffab Mba Mfbfa Mfba 7 15 Considere o diagrama positivo descrito a seguir e defina seu modelo canônico b fa ffb fffa a fb ffb b Mfaffb Mbfb Nfb Offb a a b b fa fb ffa fb ffb ffb fffa DomE a b fb ffb DestaquesE a b FunçõesE f RelaçõesE M M b a fb b ffb fb SATISFABILIDADE NA LÓGICA DE PREDICADOS 8 30 Prove através do método da resolução a seguinte afirmação xDgxVOfx xMgx xDxMx xMgxGx xOfxGx Equivalente a xDgxVOfx xMgx xDxMx xMgxGx xOfxGx ser um conjunto INSAT Skolemização xDgxVOfx xMgx xDxMx xMgxGx xOfxGx Propagação de cláusulas