of 8

A resolucao na logica de primeira ordem

21 views8 pages

Download

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
A resolucao na logica de primeira ordem
  O princípio da resolução  é uma regra de inferência que dá srcem a uma técnica de demonstração por refutação para sentenças e inferências da lógica proposicional e da lógica de primeira ordem. A resolução na lógica proposicional Regra de resolução O sistema dedutivo de resolução na lógica proposicional não possui axiomas, mas apenas uma regra de inferência que produz, a partir de duas cláusulas, uma nova cláusula implicada por elas. A regra de resolução toma duascláusulas contendo literais complementares e produz uma nova cláusula com todos os literais de amos, exclu!dos estes complementares. "ormalmente, onde and são literais complementares#A cláusula produzida pela regra de resolução é c$amada de resolvente  das duas cláusulas iniciais.%uando as duas cláusulas contêm mais de um par de literais complementares, a regra deresolução pode ser aplicada &independentemente' para cada par. (ntretanto, apenas o par de literais resolvidos pode ser removido# todos os outros pares de literais permanecem na cláusula resolvente. Uma técnica de resolução %uando usada em con)unto com um algoritmo de usca, a regra de resolução gan$a  poder e utiliza o algoritmo de usca para decidir a satisfatiilidade de uma fórmula  proposicional e a validade da sentença so um con)unto de axiomas.(sta técnica de resolução usa  prova por contradição e é aseada no fato de que qualquer sentença da lógica proposicional pode ser convertida para uma sentença equivalente na forma normal con)untiva. Os passos são os seguintes# •  Todas as premissas e a negação da sentença a ser provada ( conjectura ) tem que estar conectadas por conjunções. • A sentença resultante é convertida para a orma normal conjuntiva (tratada como um conjunto de cl!usulas" S ).  • A regra de resolução é aplicada a todos os poss#veis pares de cl!usulas que contém literais complementares. Após cada aplicação da regra de resolução" a cl!usula resultante é simpli$cada removendo%se os literais repetidos. &e a cl!usula contém literais complementares" ela é descartada (como uma tautologia). 'aso contr!rio" e se ela ainda não est! presente no conjunto de cl!usulas S " então ela é adicionada a S " e é considerada para posteriores inerncias da resolução. • &e depois de aplicar a regra de resolução uma cl!usula vaia é derivada" a ormula inteira não é satiseita (ou contraditória)" então é poss#vel concluir que a conjectura inicial provém das premissas srcinais. • &e" por outro lado" a cl!usula vaia não pode ser derivada" e a regra de resolução não pode ser aplicada para derivar mais cl!usulas" a conjectura não é um teorema da *ase de con+ecimentos srcinal. Outra inst*ncia deste algoritmo é o algoritmo de +avis-utnam srcinal, que foi mais tarde refinado para oalgoritmo +-, que removeu a necessidade de uma representação expl!cita dos resolventes./omo exemplo do algoritmo acima, considere a seguinte fórmula#%ue pode ser vista como um con)unto de cláusulas#0e)a um con)unto de cláusulas e representamos por a cláusula vazia, . Aplicase então a regra de inferência# • Aplicando a regra no con)unto de cláusulas do exemplo acima#"oi poss!vel então a dedução da cláusula vazia a partir do con)unto inicial de cláusulas. A resolução na lógica de primeira ordem A resolução na ógica de primeira ordem condensa os silogismos tradicionais de inferência lógica em uma 1nica regra. -ara entender como a resolução funciona, considere o seguinte exemplo de silogismo da lógica aristotélica# Todos os gregos são europeus.  Homero é grego.Então, Homero é europeu. Ou de maneira mais geral# X.(P(X) implica Q(X)).P(a).Então, Q(a). -ara traçar o racioc!nio usado na técnica de resolução, primeiro as cláusulas devem ser convertidas para a forma normal con)untiva. 2essa forma, todas as quantificaç3es se tornam impl!citas# quantificadores universais em variáveis &4, 5...' são simplesmente omitidos quando suentendidos, enquanto variáveis em quantificadores existenciais são sustitu!das por funç3es de 06olem. P(X) Q(X)P(a) Então, Q(a) (ntão a questão é, como a técnica de resolução deriva a ultima cláusula a partir das duas primeiras7 A regra é simples# • ,ncontre duas cl!usulas contendo o mesmo predicado" onde uma cl!usula é negada e a outra não. • -aça a uni$cação em am*os os predicados. (&e a uni$cação al+ar" então voc e uma m! escol+a de predicados. olte para o passo anterior e tente novamente.) • &e" após a uni$cação" alguma vari!vel não%ligada que oi ligada nos predicados uni$cados tam*ém ocorre em outros predicados nas duas cl!usulas" então su*stitua pelos seus respectivos termos ligados. • /escarte os predicados uni$cados" e com*ine o restante das duas cl!usulas em uma nova cl!usula. -ara aplicar essa regra no exemplo acima, nós encontramos o predicado 8-9 na forma negada na primeira cláusula# P(X) ( em forma não negada na segunda cláusula# P(a)  X   é uma variável livre, enquanto a  é um átomo. :nificando os dois otemos a sustituição#  = [(a,X)] +escartando os predicados unificados, e aplicando a sustituição dos predicados restantes &apenas %&4', nesse caso', otemos a conclusão# Q(a)  -ara um outro exemplo, considere a forma silog!stica# Todos os polticos são corruptos.Todos os corruptos são mentirosos.Então todos os polticos são mentirosos. Ou de maneira mais geral# X P(X) implica Q(X)X Q(X) implica !(X)Então, X P(X) implica !(X)  2a "2/ &"orma 2ormal /on)untiva'# P(X) Q(X)Q(") !(") &2ote que a variável na segunda cláusula foi renomeada pra deixar claro que variáveis em cláusulas diferentes são distintas'Agora, unificando %&4' na primeira cláusula com %&5' na segunda cláusula temos que 4 e 5 se tornam a mesma variável. (fetuando esta sustituição nas cláusulas restantes e cominandoas, temos a conclusão# P(X) !(X) 0ais e1emplos 2ógica 3roposicional ,1emplo 4 Socrátes e Platão • &ócrates est! em tal situação que ele estaria disposto a visitar 3latão (&)" só se 3latão estivesse disposto a visit!%lo (3)5 • 3latão est! em tal situação que ele não  estaria disposto a visitar &ócrates" se &ócrates estivesse disposto a visit!%lo5 • 3latão est! em tal situação que ele estaria disposto a visitar &ócrates"se &ócrates não  estivesse disposto a visit!%lo.  • 3ergunta%se6 0ócrates está disposto a visitar -latão ou não7;ransformação de para a forma con)untiva#;emos então o seguinte con)unto de cláusulas#<esolução#-ortanto conclu!mos que 0ócrates está disposto a visitar -latão. ,1emplo 7 Ana • &e Anelise não or cantora (3) ou Anamélia or pianista(8)" então Ana#s ser! proessora (R). • &e Ana or atleta (&)" então Anamélia ser! pianista (8). • &e Anelise or cantora (3)" então Ana ser! atleta (&).
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks