Introdução à Lógica de Predicados

Aula Lógica de Predicados Introdução A linguagem da lógica proposicional vista em aulas anteriores é limitada para representar relações entre objetos do mundo real Por exemplo se usássemos a linguagem proposicional para representar as sentenças Todos são mortais e Alguém é bondoso utilizaríamos duas proposições quaisquer sem decompor em sentenças menores ligadas pelos conectivos lógicos Outra limitação da lógica proposicional é a que esta linguagem tem baixo poder de expressão pois é incapaz de representar instâncias de uma propriedade geral Para sanar problemas deste tipo surgiu então a lógica de predicados que é uma extensão da lógica proposicional Aranha e Martins 2003 A lógica de predicados é também conhecida na literatura como lógica de primeira ordem ou cálculo de predicados Esta lógica possibilita captar relações entre indivíduos de um mesmo domínio e permitir concluir particularidades de uma propriedade geral dos indivíduos de um domínio assim como derivar generalizações a partir de fatos que valem para um indivíduo qualquer do domínio Desta maneira expressar sentenças com as palavras existe qualquer todos alguns e somente por exemplo é possível Para ter este grande poder de expressão a lógica de predicados dispõe uma variedade de símbolos Então vamos conhecer o seu alfabeto inicialmente e em seguida como representar conhecimento relações entre objetos mais especificamente 1 Alfabeto O alfabeto da linguagem da lógica de predicados consiste em símbolos lógicos e nãológicos Os símbolos lógicos são caracterizados por pontuação conectivos quantificadores Os símbolos nãológicos são definidos por variáveis por convenção letras do fim do alfabeto tais como x y z constantes por convenção letras do início do alfabeto tais como a b c predicativos ou predicados por convenção letras do meio para o fim do alfabeto tais como p q r ou uma palavra em letras minúsculas para ser mais representativa Ù Ú Como dito anteriormente a lógica de predicados é uma extensão da lógica proposicional e desta maneira tanto os símbolos de pontuação quanto os conectivos lógicos possuem o mesmo significado Com relação aos quantificadores temse o universal e existencial para expressar propriedades que valem para todos os indivíduos do domínio ou para alguns indivíduos do domínio respectivamente Estes quantificadores estarão sempre acompanhados de uma variável símbolo nãológico para captar o conceito das palavras para qualquer e para algum respectivamente É importante ressaltar que variáveis diferentes não designam necessariamente objetos diferentes e que a escolha de variáveis não faz diferença para o significado Franco 2008 O ingrediente novo da lógica de primeira ordem não encontrado na lógica proposicional é a quantificação Wikipédia 2008 As variáveis nesta lógica designam a representação de um exemplo ou indivíduo do domínio que está se referindo Assim podemos dizer por exemplo que existe um aluno inteligente na sala de aula porém esta pessoa não está sendo especificada e sim informando a existência de tal fato Portanto uma variável representa um elemento de quaisquer domínio de aplicação As constantes por sua vez são usadas para definir ou especificar um determinado indivíduo do domínio Considerando ainda o exemplo anterior poderíamos definir que João é o aluno inteligente da sala de aula Observe que neste caso estamos definindo exatamente quem é a pessoa inteligente da sala Cada constante indica exatamente um objeto particular Os símbolos predicativos ou predicados representam o conceito de relação entre um ou mais indivíduos de um domínio Com este tipo de símbolo poderíamos criar um predicado chamado pai para representar a relação de parentesco entre João e Ana por exemplo conforme o conhecimento fornecido no início desta aula Os predicados nomes de relação podem possuir um ou mais argumentos A definição da quantidade de argumentos num predicado dependerá da forma como os relacionamentos entre os objetos estão sendo tratados Com relação à quantidade de argumentos que um predicado possui chamamos de aridade Por exemplo os predicados vereadorjuarez e paijoão ana têm aridade igual a um e dois respectivamente No primeiro predicado representamos que Juarez é um vereador e neste caso a leitura deste predicado iniciase pela constante juarez e depois lêse o nome do predicado vereador No segundo exemplo representamos que João é pai de Ana e a forma de leitura começa com o primeiro parâmetro joão depois analisa o nome do predicado pai e em seguida retorna ao segundo parâmetro ana 2 Interpretação Como a lógica de predicados possui um alfabeto bem mais diversificado se comparado com o da lógica proposicional as interpretações das fórmulas tornamse naturalmente mais bem elaboradas Observe a seguir a simbologia da lógica de primeira ordem em quatro sentenças bastante conhecidas na literatura bem como a sua forma de leitura conforme pode ser encontrado em Abar 2008 Todo s é p Usando a letra como uma variável para representar objetos individuais expressamos tal enunciado por qualquer que seja se é então é Outras opções de leitura são são cada é um qualquer é um e todos os objetos que tem propriedade são objetos que tem propriedade Sendo assim podemos inferir que Todo s é p está relacionado a uma universal afirmativa Alguns s são p Neste caso o enunciado pode ser expresso por para pelo menos um é e é Outras opções de leitura são existem que são e há que são Este exemplo ao contrário do enunciado anterior restringe um certo grupo do todo e assim está relacionando uma particularidade afirmativa Alguns s são não p Para esta situação temos a interpretação que existe um tal que é e não é Podemos ainda ler esta sentença como alguns não são certos não são existem que não são e pelo menos um não é Observando este enunciado identificamos que existe uma seleção do todo porém com aspecto de negação Assim dizemos que obtemos uma particularidade negativa Nenhum s é p Nesta última sentença temos qualquer que seja se é então não é É possível ainda ler esta sentença como ninguém que seja é nada que seja p x x s x x x x s x p s p s p s p s p p x x s x Ù x x s x p s p s p p x x s x Ù x x s x p s p s p s p s p p x x s x x x s x p s p é e nenhum dos é Neste exemplo obtemos uma generalização negativa pois qualquer que seja este não é Assim a partir da linguagem natural usada no cotidiano podemos expressar a mesma idéia utilizando o alfabeto da lógica de predicados Nestes últimos exemplos foram usados os predicados e os quais não expressam muita informação para o usuário Por isso é importante que se apresente nomes de predicados condizentes com o que se deseja representar uma vez que estes auxiliam à interpretação do pensamento Vale a pena lembrar que a definição de um nome do predicado é de sua escolha Veja na tabela a seguir alguns exemplos do uso desta representação sendo neste caso com nomes de predicado mais significativos Tabela 1 Linguagem Natural e Lógica de Predicados Linguagem Natural Lógica de Predicados Todos os homens são mortais xhomemx mortalx Alguns gatos são bonitos xgatox bonitox Nenhuma baleia é réptil xbaleiax réptilx Meninos e meninas gostam de brincar xmeninox meninax gostabrincarx Há pintores que não são artistas mas artesãos xpintorx artistax artesãox João não foi o primeiro homem xhomemx nasceuantesx joão Todos os números ímpares não são divisíveis por 2 xnúmerox ímparx divisívelx2 Todos os cachorros são protegidos pelos homens x yhomemx cachorroy protegexy Todas as crianças são mais jovens que seus pais x ycriançax paiy x jovemx y Como você deve ter observado numa mesma fórmula pode existir mais de um quantificador conectivo variável ou predicado Analisando a frase Meninos e meninas gostam de brincar por exemplo observamos que a conjunção e apresentada na sentença não está expressa na sua fórmula Na verdade ao invés do e temse a representação do OU E neste caso a representação está correta A resposta é sim pois avaliando a fórmula veremos que a variável x que é um elemento do domínio pode ser um menino ou uma menina somente nunca os dois ao mesmo tempo E ou menino ou menina seja este ou esta gosta de brincar Com relação à sentença Todas as crianças são mais jovens que os pais observe que foram utilizados dois quantificadores universais um com a variável x e outro com a variável y Para expressar que uma criança é mais jovem que pai s p s p x p s p Ù Ú Ù Ù Ù Ù Ù Ù Ú apresentamos inicialmente a condição necessária para que isto aconteça Ou seja é preciso que o x seja uma criança e o y seja o pai da criança Caso positivo então podemos inferir que o x é mais jovem do que o y Ao fazer o uso dos quantificadores é possível observar a existência de 4 situações A Universal Afirmativa E Universal Negativa I Particular Afirmativa e O Particular Negativa conforme mostra a Figura 1 Figura 1 Abrangência dos Quantificadores adaptado de Soares 2003 Nesta figura é possível observar quando se acompanha as linhas verticais tem se uma generalização baixo para cima ou uma restrição cima para baixo Ambas informam a mesma verdade ou falsidade porém diferenciam em termos de quantidade Ao acompanhar a linha horizontal mais inferior observase uma oposição parcial de um lado para o outro pois apenas o valor de um predicado está sendo alterado opondose assim em termos de qualidade Já na linha horizontal superior temse uma oposição em termos de qualidade porque uma afirma e outra nega um mesmo predicado de um mesmo sujeito universalmente E por fim as diagonais apresentam a oposição mais forte porque não há nada que se possa convir se opondo em termos de quantidade e qualidade 3 Equivalências Lógicas A lógica de predicados é uma linguagem utilizada para a representação de conhecimento observando os objetos existentes e os relacionamentos entre eles Dentre as linguagens de representação disponíveis a lógica de predicados é uma das linguagens mais estudadas porque esta pode ser aplicada em diversos domínios Russell e Norvig 2003 Para esta representação podemos usar diferentes maneiras para expressar a mesma idéia ou conceito Se quiséssemos representar o conceito de que nem todos os indivíduos possuem a propriedade p poderíamos usar a representação Neste caso x p x p x x s x Ù p x x s x Ù p x x s x p x x s x A Universal Afirmativa Ex Toda aula é expositiva E Universal Negativa Ex Nenhuma aula é expositiva I Particular Afirmativa Ex Alguma aula é expositiva O Particular Negativa Ex Alguma aula não é expositiva usamos o quantificador universal com o conectivo de negação informando que não é verdade que todo tem a propriedade Além disso para expressar esta mesma idéia podemos utilizar também o quantificador existencial Neste caso teremos a expressão Para este caso informamos que existe pelo menos um que não tem a propriedade Ambas representações são válidas para a expressão de que nem todos os indivíduos possuem a propriedade Logo concluímos que e são equivalentes logicamente ou seja E se agora quiséssemos representar o conceito de que não existe um indivíduo do domínio que possua a propriedade Para esta situação poderíamos usar o quantificador existencial com o conectivo da negação como por exemplo Observe que o conectivo de negação está externo negando toda a expressão e assim representando que não existe um que tem a propriedade De forma similar à situação anterior este conceito pode ainda ser expresso com o quantificador universal Neste caso temos em que todo não tem a propriedade Portanto concluímos que as expressões e são equivalentes ou seja É importante lembrar que como estas representações são equivalentes logicamente ambas podem ser usadas indistintamente Além dessas equivalências apresentadas podemos ainda mencionar as seguintes equivalências No primeiro caso temos que todo tem a propriedade é equivalente a dizer que não é verdade que um tal que não possui a propriedade representado por Já para o segundo caso temos que existe pelo menos um tal que tem a propriedade Assim poderíamos expressar a mesma idéia com o uso do quantificador universal informando que não é verdade que todo não tem a propriedade Enfim para todas essas situações o papel fundamental da equivalência é possibilitar a substituição de uma fórmula pela a outra sem perdas lógicas Com isso recomendase o uso da versão em que seja mais familiar e compreensiva 4 Implicações Lógicas x p x p x x p p x p x x p x x p x Û x p x p x p x x p x p x x p x p x x p x x p x Û x p x x p x Û x p x x p x Û x p x x p x p x x p x p x x p x p x x p x p x y xP x y x yP x y Þ 5 Negação de Quantificadores A negação de uma proposição que contenha um quantificador exige certos cuidados tendo em vista a natureza do quantificador e do predicado pois não é a mesma coisa negar o quantificador e negar o predicado Seja por exemplo Se Px é o predicado x é um gato preto temse 1 x Px significa todos os gatos são pretos 2 x Px significa todos os gatos não são pretos 3 x Px significa nem todos os gatos são pretos Neste caso o item 2 é a negação do predicado enquanto o item 3 é a negação do quantificador A proposição 3 negação do quantificador universal é equivalente a existem gatos que não são pretos ou existe pelo menos um gato que não é preto Disto se conclui x Px Û x Px É possível resumir a negação dos quantificadores em 2 grupos que são A negação de Todo A é B é Algum A não é B e viceversa É só seguir a linha diagonal na Figura 1 A negação de Algum A é B é Nenhum A é B e viceversa É só seguir a linha diagonal na Figura 1 A negação de Todos brasileiros comem churrasco é Não é verdade que todos brasileiros comem churrasco Assim considerando Cx uma função que representa que x come churrasco então a negação seria formalizada como xCx que equivale a xCx Em linguagem natural essa expressão pode ser dita como Existe um brasileiro que não come churrasco ou ainda Alguns brasileiros não comem churrasco Atividades Q x xP x xQ x xP x Ú Þ Ú Q x xP x Q x xP x Ù Þ Ù Q x x P x xQ x xP x Ú Þ Ù 1 Formalize os enunciados a seguir usando o alfabeto da lógica de primeira ordem a Nenhum tubarão é considerado uma pessoa b Nem todos os tubarões são carnívoros c Só verdadeiros e falsos são valores lógicos d Todos os tubarões têm dentes afiados 2 Relacione a primeira coluna com a segunda de forma que ambos expressem o mesmo conhecimento embora estejam usando linguagens diferentes Considere ainda que representa é um feiticeiro representa é um humano representa x é um número par e representa é um número primo I II III x y y x py IV Para todo número existe um outro número que é maior ou igual a ele e é par Existem feiticeiros humanos Nem todo homem é feiticeiro Existem números pares e primos a III II I IV b IV I II III c IV II I III d III I II IV 3 Considerando que a relação representa é avô de y e representa é pai de escreva usando a linguagem natural a seguinte expressão 4 A partir da linguagem da lógica de predicados é possível representar o mesmo conhecimento de diversas formas Sendo assim analise as frases Alguns peixes são surubim e Nenhum peixe é surubim e em seguida assinale a alternativa que possua sua representação da forma correta a x peixex surubim x x peixex surubimx f x x hx x x p prx x h x x f x Ù f x x h x ³ Ù pr x x p x Ù a x y x p x y x y p g y g p x g x y a x y Ù Ú b x peixex surubim x x peixex surubimx c x surubim x peixe x x peixex surubimx d x peixex surubim x x peixex surubimx 5 Represente as seguintes frases utilizando o alfabeto da lógica de predicados a Nenhum argumento com premissas verdadeiras e conclusão falsa é um argumento válido b Todo argumento correto tem conclusão verdadeira c Todo argumento com premissas falsas e inválido tem conclusão falsa d Nem todo argumento inválido e com premissas verdadeiras tem conclusão falsa e Nenhum argumento correto tem conclusão falsa f Todo argumento com conclusão falsa é inválido g Não existem argumentos corretos com conclusão falsa h Existem argumentos inválidos com conclusão verdadeira 6 Utilizando a linguagem da lógica de predicados formalize os argumentos apresentados a seguir a Nenhum político é sincero Alguns políticos são advogados Logo alguns advogados não são sinceros b Fernando Collor foi presidente do Brasil Fernando Collor foi destituído da presidência através de um processo de impeachment Logo existe pelo menos um presidente que foi destituído através de um processo de impeachment c Todos os senadores são eleitos pelo povo Posto que alguns senadores são desonestos podese concluir que existem pessoas desonestas eleitas pelo povo d Alguns políticos são desonestos Alguns advogados são políticos Logo alguns advogados são desonestos e Nenhum deputado governista vai votar contra as reformas Pedro não é um deputado governista Logo Pedro vai votar contra as reformas f Há monitor que é bom estudante mas não é comunicativo Apenas bons estudantes são monitores Todo artista é comunicativo Portanto nem todo bom estudante é um artista g Alguns escritores são poetas Nenhum músico é poeta Logo nenhum músico é escritor h Alguns escritores são poetas Nenhum músico é poeta Logo existem escritores que não são músicos Ù Ù Ú i Todo psiquiatra é médico Nenhum engenheiro de software é médico Portanto nenhum psiquiatra é engenheiro de software j Todo trabalhador é responsável Todo artista se não for filósofo ou é trabalhador ou é poeta Não há filósofo e não há poeta que não seja responsável Portanto todo artista é responsável 7 Considerando que os predicados Px e Qx significam x é divisível por 2 e x é divisível por 3 respectivamente traduza as fórmulas abaixo para a linguagem natural língua portuguesa levando em consideração o significado do alfabeto da lógica de predicados a x Px b x Px c x Px d x Px e x Px f x Px Ù Qx g x Px Ú Qx 8 Formalize os enunciados a seguir usando o alfabeto da lógica de primeira ordem a Todos os programas funcionam b Nenhum programa funciona c Alguns programas funcionam d Alguns programas não funcionam e Qualquer coisa funciona f Alguma coisa funciona g Nem tudo funciona h Nada funciona i João ama a si próprio j João ama todo mundo k Todo mundo ama João l Qualquer pessoa ama a si mesma m Existe alguém que se ama n Existe alguém que Maria não ama o Existe alguém que tanto João quanto Maria amam p Todo mundo ama todo mundo q Alguém ama alguém r Existe alguém que ama todo mundo s Todo mundo é amado por alguém t Todo aluno é mais novo do que algum professor u Nem todos os pássaros são capazes de voar v Algumas coisas estão ligadas e outras não estão w Qualquer coisa ou está ligada ou não está ligada x Todos os programas são programas y Somente programas funcionam z Existe pelo menos um gaúcho aqui aa Existe pelo menos um número que é menor que 2 bb Todo homem é imaginativo cc Alguns homens são bombeiros dd Alguns alunos são baianos 9 Represente o conhecimento apresentado a seguir usando a linguagem de primeira ordem a Premissa1 Todos os homens são mortais Premissa2 Sócrates é homem Conclusão Portanto Sócrates é mortal b Premissa1 Toda baleia é um mamífero Premissa2 Todo mamífero tem pulmões Conclusão Portanto toda baleia tem pulmões c Premissa1 Jeremias é rico Premissa2 Todos os homens ricos são felizes Conclusão Logo Jeremias é feliz d Premissa1 Alguns felinos são tigres Premissa2 Todos os tigres são belos Conclusão Logo alguns felinos são belos e Premissa1 Todos os sãocarlenses são paulistas Premissa2 Todos os paulistas são brasileiros Conclusão Logo todos os sãocarlenses são brasileiros f Premissa1 Nenhuma baleia é peixe Premissa2 Moby Dick é baleia Conclusão Logo Moby Dick não é peixe g Premissa1 Todo amigo de Carlos é amigo de Jonas Premissa2 Pedro não é amigo de Jonas Conclusão Logo Pedro não é amigo de Carlos h Premissa1 Todos os cientistas são estudiosos Premissa2 Alguns cientistas são inventores Conclusão Alguns estudiosos são inventores i Premissa1 Todos os humanos são racionais Premissa2 Alguns animais são humanos Conclusão Portanto alguns animais são racionais 10 ENADE 2008 Uma fórmula bem formada da lógica de predicados é válida se ela é verdadeira para todas as interpretações possíveis Considerando essa informação analise as duas asserções apresentadas a seguir A fórmula bem formada x Px Þ x Px é válida porque em qualquer interpretação de uma fórmula da lógica de predicados se todo elemento do conjunto universo tem a propriedade P então existe um elemento do conjunto que tem essa propriedade Assinale a opção correta com relação a essas asserções a As duas asserções são proposições verdadeiras e a segunda é uma justificativa correta da primeira b As duas asserções são proposições verdadeiras e a segunda não é uma justificativa correta da primeira c A primeira asserção é uma proposição verdadeira e a segunda é uma proposição falsa d A primeira asserção é uma proposição falsa e a segunda é uma proposição verdadeira e As duas asserções são proposições falsas 11 SERPRO Analista de Sistemas2005 Considere a seguinte argumentação lógica Todo psiquiatra é médico Nenhum engenheiro de software é médico Portanto nenhum psiquiatra é engenheiro de software Denote por x um indivíduo qualquer e simbolize por Px o fato de o indivíduo ser psiquiatra por Mx o fato de ele ser médico e por Ex o fato de ser engenheiro de software Nesse contexto e com base na argumentação lógica julgue os itens seguintes 1 A argumentação lógica pode ser simbolizada por x Px Mx x Ex Ù Mx x Px Ù Ex 2 A forma simbólica x Ex Ù Mx é logicamente equivalente a x Ex Ù Mx 12 Escreva em linguagem natural a negação das seguintes afirmações a Todos os cargos deste concurso são de analista de informática b Alguns escritores são poetas c Nenhum engenheiro de software é médico d Alguns políticos não são honestos e Pelo menos um economista não é médico f Todos os não médicos são não economistas g Existem pessoas inteligentes que não sabem ler ou escrever h Toda pessoa culta é sábia se e somente se for inteligente 13 Todos os alunos de matemática são também alunos de inglês mas nenhum aluno de inglês é aluno de história Todos os alunos de português são também alunos de informática e alguns alunos de informática são também alunos de história Como nenhum aluno de informática é aluno de inglês e como nenhum aluno de português é aluno de história então a pelo menos um aluno de português é aluno de inglês b pelo menos um aluno de matemática é aluno de história c nenhum aluno de português é aluno de matemática d todos os alunos de informática são alunos de matemática e todos os alunos de informática são alunos de português 14 Um contraexemplo para Todo homem cristão é um homem penitente é encontrar a um homem não cristão que seja penitente b um homem que não seja penitente nem cristão c uma mulher cristã e penitente d um homem que não seja penitente e que seja cristão e uma mulher cristã e que não seja penitente