Lista de Exercicios Resolvidos - Lógica de Predicados 1

Lógica de Predicados 1 Determine o comprimento e as subfórmulas das seguintes fórmulas a pX Y fZ Comprimento 1 Subfórmula pX Y fZ b pX Y XqX Comprimento 4 Subfórmulas pX Y XqX pX Y XqX qX 2 Marque a fórmula que é equivalente à NEGAÇÃO de V pV X qX YZ rY Z a V pV X qX YZ rYZ b V pV X qX YZ rYZ c V pV X qX YZ rYZ V pV X qX YZ rY Z V pV X qX YZ rY Z V pV X qX YZ rY Z V pV X qX YZ rY Z V pV X qX YZ rY Z V pV X qX YZ rY Z letra a 3 Marque a equivalência válida W é uma fórmula na qual a variável X não ocorre livre a X pX W X pX W X pX W X pX W X pX X W X pX W X pX W b X pX W X pX W X pX W X pX X W X pX W c X pX W X pX W X pX W X pX W X pX X W X pX W X pX W Essa é a resposta 4 Assinale as afirmações como verdadeiras ou falsas Atenção cada marcação errada anula uma marcação correta a Toda variável é um termo Verdadeiro Por definição termos são variáveis e funções b Toda variável é um átomo Falso Variável é um termo c Todo termo é uma fórmula Falso Fórmulas são átomos ou conectivos e quantificadores aplicados sobre fórmulas d Todo átomo é uma fórmula Verdadeiro Por definição e Todo literal é uma fórmula Verdadeiro Literais são átomos ou suas negações então são fórmulas f Todo átomo é um literal Verdadeiro Por definição g Se G é tautologia todo tableau associado a G é fechado Falso Pode haver tableau aberto associado a G h Se um tableau de G é fechado G é tautologia Verdadeiro G é tautologia se e somente se pelo menos um tableau associado a G é fechado i Toda expansão por resolução é finita Falso A expansão por resolução pode se estender indefinidamente j A resolução de duas cláusulas que têm no máximo um literal positivo gera uma cláusula com no máximo um literal positivo Verdadeiro Ao fazer a resolução serão removidos um literal positivo e um literal negativo como existem no máximo dois literais positivos um de cada cláusula o resultado tem no máximo um literal positivo k Uma cláusula com um único literal é chamada de cláusula unitária A resolução de duas cláusulas unitárias é a cláusula vazia Verdadeiro Se a resolução pode ser feita um par de literais serão removidos Como só temos dois literais o resultado é vazio l Todo tableau associado a uma fórmula insatisfatível é fechado Falso Isso só é verdade para a lógica proposicional Na lógica de predicados existe pelo menos um tableau fechado associado a uma fórmula insatisfatível não necessariamente todos são fechados m Um programa lógico sem cláusulas unitárias é incapaz de gerar qualquer resultado positivo Verdadeiro A cláusula de consulta só se reduz de tamanho quando é resolvida com uma cláusula unitária Portanto só é possível chegar na cláusula vazia se existem cláusulas unitárias n Se G é tautologia há uma resolução fechada associada a G Verdadeiro G é tautologia se e somente se pelo menos uma resolução associado a G é fechada 5 Escreva a seguinte fórmula na notação de conjuntos X Y qY X Y Z rX Y Z Muita gente começou negando a fórmula não deveria ter feito isso O que foi pedido foi a representação desta fórmula e não da negação dela Vamos remover o primeiro quantificador existencial porque X não ocorre em seu escopo O segundo Y foi renomeado para W Y qY X W Z rX W Z Internalização da negação Y qY X W Z rX W Z A partir deste ponto temos duas possibilidades de continuação Possibilidade 1 Forma Prenex Y X W Z qY rX W Z Skolemização Y W qY rfY W gY W Notação de Conjuntos qY rfY W gY W Possibilidade 2 Forma Prenex X W Z Y rX W Z qY Skolemização W Y ra W fW qY Notação de Conjuntos qY ra W fW 6 Demonstre por resolução ou tableau se a seguinte fórmula é satisfatível pX Y pY X pZ Z pQ R pS R pS R A questão é sobre satisfatibilidade se há tableau ou resolução fechada associada à fórmula então ela é insatisfatível caso contrário é satisfatível A maioria começou negando a fórmula a partir da negação concluímos se ela é tautologia ou não Dava pra ter uma intuição de que ela é insatisfatível porque a primeira regra diz que se pXY é verdade pYX é falsa A segunda afirmação é que pZZ é verdade Juntando as duas afirmações temos que pZZ deve ser verdadeiro e falso simultaneamente para satisfazer a fórmula Por resolução Primeiro vamos escrever a fórmula na PrenexFNC pX Y pY X pZ Z pQ R pS R pS R pX Y pY X pZ Z pQ R pS R pS R pX Y pY X pZ Z pQ R pS R Notação de conjuntos pX Y pY X pZ Z pQ R pS R Resolução 1 pX Y pY X 2 pZ Z 3 pQ R pS R 4 pZ Z R1 2 X Z Y Z 5 R4 5 Por tableau Para acelerar alguns passos visto que todas as variáveis estão quantificadas universalmente e que as eliminações desses quantificadores serão os primeiros passos da expansão desta fórmula por tableau vamos substituir todas as variáveis pela constante c em um único passo pX Y pY X pZ Z pQ R pS R pS R pc c pc c pc c pc c pc c pc c pc c pc c pc c pc c pc c pc c pc c pc c fechado fechado 7 Selecione a fórmula que representa a seguinte afirmação Nenhum dos meus amigos é perfeito Nas fórmulas o predicado aX significa X é meu amigo e pX significa X é perfeito a X aX pX Existe alguém que é meu amigo e não é perfeito Isso não impede que algum seja portanto não é a frase do enunciado b X aX pX Existe alguém que não é meu amigo e não é perfeito A frase não fala nada sobre as pessoas que não são meus amigos c X aX pX Existe alguém que não é meu amigo e é perfeito A frase não fala nada sobre as pessoas que não são meus amigos d X aX pX Não existe alguém que é meu amigo e é perfeito Portanto nenhum dos meus amigos é perfeito resposta correta 8 Considere que o predicado eqXY significa que X é igual a Y e a função mXY é o produto de X por Y Definimos o predicado pX como pX eqX 1 Y Z eqX mY Z eqY X eqY 1 Assinale a afirmação correta a Se pX é verdade então X é um número primo b Se pX é verdade então X não é um número primo Para pX ser verdade se X é escrito como o produto de Y por Z Y é igual a X e daí Z é 1 ou Y é igual a 1 logo Z é X Ou seja X só tem dois fatores 1 e ele mesmo Portanto a resposta é a letra a 9 Considere a afirmação objetos de ouro são valiosos objetos de prata também são Considere os predicados oX X é de ouro pX X é de prata e vX X é valioso Qual fórmula representa essa afirmação a X oX pX vX Se um objeto é de ouro e prata então ele é valioso Essa frase não está errada mas não é a frase do enunciado O objeto não precisa ser simultaneamente de ouro e prata b X oX pX vX Se um objeto é de ouro eou prata então ele é valioso Essa é a frase do enunciado O objeto pode ser só de ouro ou só de prata ou ambos Em todos os casos ele é valioso resposta correta c X vX oX pX Se um objeto é valioso ele é de ouro eou prata Não é isso que foi dito no enunciado talvez ele seja valioso e não seja feito destes materiais 10 Considere a afirmação nem todo dia chuvoso é frio e os predicados cX X é um dia chuvoso e fX X é um dia frio Qual a fórmula que representa a afirmação a X cX fX Todo dia chuvoso não é frio b X cX fX X cX fX Todo dia chove ou faz frio Os dias que são simultaneamente chuvosos e frios satisfazem essa fórmula que é diferente do que foi dito enunciado c X cX fX X cX fX Existe pelo menos um dia que chove ou faz frio Isso pode até ser verdade mas não é equivalente à frase do enunciado d X cX fX Existe dia que é chuvoso e não é frio X cX fX X cX fX Nem sempre se chove faz frio resposta correta 11 Considere a afirmação Ou 2 X 1 ou 1 X 2 Qual das opções representa o complemento dessa afirmação a X 2 ou X 2 ou 1 X 1 b X 2 ou X 2 c 1 X 1 d X 2 ou 2 X ou 1 X 1 Como os intervalos são fechados o complemento será aberto Fora do intervalo definido temos X 2 ou X 2 ou 1 X 1 resposta correta letra a 12 Um mapa de um certo jogo é formado por várias salas numeradas Algumas salas estão conectadas através de portais unidirecionais Ou seja se há um portal de 1 para 2 é possível ir da sala 1 para a sala 2 mas o contrário não é verdade Considere a seguinte lista de portais onde pX Y indica que Há um portal de X para Y p12 p34 p56 p78 p910 p1213 p1314 p1516 p1718 p1920 p41 p63 p47 p611 p149 p1115 p1612 p1417 p1619 a Escreva um predicado vaiXY que significa A sala Y pode ser alcançada a partir da sala X em um ou mais passos É a mesma idéia do descendente que fizemos como exemplo em aula vaiX Y é verdade se é possível dar um passo de X pra Y ou se é possível dar um passo de X para Z e há um caminho de um ou mais passos de Z para Y vaiX Y pX Y vaiX Y pX Z vaiZ Y b Há alguma sala inalcançável a partir das demais Sim a sala 5 Ela nunca aparece no segundo argumento do predicado p então nenhum portal leva a ela c Quais salas quando alcançadas deixam o jogador preso As salas 2 8 10 18 e 20 Elas nunca aparecem no primeiro argumento do predicado p então nenhum portal sai delas 13 Considere os seguintes predicados com informações sobre viagens onibusrecife maceio onibusmaceio aracaju onibusliege cologne onibusliege lille tremlille frankfurt tremcologne frankfurt tremlille paris tremcologne paris aviaofrankfurt bangkok aviaofrankfurt singapura aviaoparis losAngeles aviaobangkok recife aviaosingapura recife aviaolosAngeles recife onde carroXY indica que é possível ir de carro de X para Y tremXY indica que é possível ir de trem de X para Y e aviaoXY indica que é possível ir de avião de X para Y a Escreva um predicado viagemXY que determina se é possível ir de X para Y através de alguma combinação de deslocamentos Ex viagemparis aracaju deve retornar True É a mesma idéia da questão anterior Existem 3 formas de dar um passo de onibus trem ou avião Então o predicado pX Y foi criado para não ter que repetir os 3 casos o tempo todo pX Y é verdade se há um caminho direto de X para Y independentemente do meio de transporte pX Y onibusX Y tremX Y aviaoX Y viagemX Y pX Y viagemX Y pX Z viagemZ Y b Saber que é possível viajar é uma informação interessante mas melhor ainda seria saber qual sequência de viagens devem ser feitas Escreva um predicado viagemXYZ que diz a rota que deve ser feita Por exemplo para a consulta viagemparis aracaju Z o Prolog deve retornar Z viagemparis losAngeles viagemlosAngeles recife viagemrecife maceio viagemmaceio aracaju Mesma idéia de antes só vamos acrescentar uma variável para guardar a informação que queremos Se há um caminho direto de X para Y essa terceira variável será viagemX Y Se há um caminho indireto passando por Z anotase viagemX Z A onde A vai ser unificado com o resto do caminho pX Y onibusX Y tremX Y aviaoX Y viagemXY viagemXY pX Y viagemXY viagemXZA pX Z viagemZ Y A c Estenda o predicado definido anteriormente para dizer que tipo de transporte deve ser utilizado nas transições Para a consulta viagemparis aracaju Z o programa deve retornar Z viagemparis losAngeles aviao viagemlosAngeles recife aviao viagemrecife maceio onibus viagemmaceio aracaju onibus Mais uma vez a mesma idéia agora o predicado p vai guardar também qual o meio de transporte utilizado Ao anotar a viagem vamos apenas acrescentar o meio de transporte pX Y onibus onibusX Y pX Y trem tremX Y pX Y aviao aviaoX Y viagemXY viagemXYT pXYT viagemXY viagemXZTA pXZT viagemZYA 14 Vamos criar predicados para retornar listas de inteiros em um dado intervalo a Crie o predicado listaI S L que vai unificar em L uma lista contendo todos os inteiros de I até S Exemplo de consulta lista2 3 L L 2 1 0 1 2 3 listaIII listaISIT I S I1 is I 1 listaI1ST b Crie o predicado listaS L que vai unificar em L uma lista contendo os naturais de 0 até S Exemplo de consulta lista3 L L 0 1 2 3 Assumindo que o predicado da letra a já foi definido listaS L lista0 S L Muita gente usou predicados prédefinidos do Prolog como numList between e findall Funciona mas não precisava porque o predicado lista definido na letra a já faz o mesmo que o numList c Crie o predicado listaL que vai unificar em L uma lista contendo os naturais de 0 a 10 Exemplo de consulta listaL L 0 1 2 3 4 5 6 7 8 9 10 Assumindo que o predicado da letra b já foi definido listaL lista10 L Outra solução bem simples era especificar a lista que se quer como retorno lista0 1 2 3 4 5 6 7 8 9 10 15 Matrizes são geralmente representadas em linguagens de programação através de listas de listas A matriz 1 2 3 4 A 5 6 7 8 9 10 11 12 Pode ser representada no Prolog como A 1 2 3 4 5 6 7 8 9 10 11 12 a Para ser uma matriz todas as linhas precisam ter o mesmo comprimento Crie um predicado matrizM que verifica se M é uma matriz ou não Essa função comp faz o mesmo que a função length já definida no Prolog Só pra mostrar que não precisava usar nenhuma função prédefinida comp 0 compT N compTX N is X1 Essa é a função que faz de fato o que é pedido Ao chamar matrizM o comprimento da primeira linha é unificado com C e é chamado matrizRL C onde RL são as demais linhas A partir daí o processo se repete o comprimento da primeira linha de RL é calculado e unificado com C que vai ser falso se for diferente do comprimento da primeira linha Se todas as linhas foram comparadas contra a primeira e passaram no teste chegamos no caso base matriz matrizLRLC compLC matrizRLC matrizLRL compLC matrizRLC Muitas soluções usaram os predicados prédefinidos aggregate member mapList max e min Crianto uma lista com o comprimento de todas as linhas e verificando se o máximo e o mínimo desta lista são iguais ou não Funciona mas não precisava b Crie um predicado transpoeM T que unifica em T a transposta da matriz M Exemplo de consulta transpoe1234 5678 9101112 T T 1 5 9 2 6 10 3 7 11 4 8 12 1 5 9 A T 2 6 10 3 7 11 4 8 12 A primeira linha da matriz transposta é formada pela cabeça de cada uma das listas da matriz M Se aplicarmos de novo a mesma função ao resto da matriz sem o primeiro elemento de cada linha temos a segunda linha da matriz transposta e assim sucessivamente matrizM só verifica se a entrada é uma matriz válida usando o predicado da letra a pode ser removida sem grandes prejuízos transpoe transpoeM LL1 matrizM cabecasM L R transpoeR L1 A função cabeças cria uma lista segundo argumento com as cabeças da matriz primeiro argumento e o resto fica no terceiro argumento Isso é feito linha a linha de forma recursiva cabecas cabecasXYT XX1 YY1 cabecasT X1 Y1