Fundamentos Matemáticos para Computação - Lógica de Predicados (Libras)

[Música] Olá alunas e alunos do curso de fundamentos matemáticos para computação nesta vídeo aula eu vou falar da lógica de predicados começar apresentando regras de dedução considerando a particularização Universal e a particularização existencial depois apresentar a generalização Universal e existencial por último Vamos eu vou ilustrar o uso dessas regras através de exemplos bom é diferente da lógica proposicional que poderíamos provar a validade de um argumento usando por exemplo uma tabela verdade na lógica de predicado nós utilizamos um sistema mais formal sistema de regras de dedução para partir dessas hipóteses e chegar à conclusão desejada para

isso tá sistema ele deve ser correto no sentido de que apenas argumentos válidos vão ser demonstráveis né e as hipó verdadeiras dentro de um domínio de interpretação vão levar com a aplicação das regras de dedução a conclusões que também são verdadeiras dentro desse domínio de interpretação então também se trata de um sistema que é completo no sentido de que todo argumento válido ele deve ser demonstrado demonstrado Além disso ele busca ser tratado no sentido da gente conseguir realizar a pele deduções com um conjunto aplicando um conjunto mínimo de regras bom as regras de equivalência e

as regras de inferência que vimos lá nas lojas na lógica proporcional ainda vão fazer parte desse sistema de loja de formal de dedução na lógica de predicados tá então por exemplo aqui nós temos essa esse argumento na lógica de predicados onde podemos identificar que essa hipótese e essa aqui então temos duas hipóteses se observamos é sendo essa hipótese verdadeira e essa aqui também verdadeira esse antecedente válido nos leva a inferir que esse consequente aqui também é válido que é a regra de motos que vimos sendo aplicada na linha 1 e 2 bom mas a abordagem

geral na para Se provar algo em lógica de predicado é tentar trazer dessa lógica de predicado para um esquema de lógica proposicional para situações particulares então é retirar os modificadores e manipular a gente faz isso retirando os quantificadores e manipulando as fórmulas bem informadas sem esses codificadores e depois a gente retorna com eles dependendo da conclusão que a gente quer chegar para isso então nós vamos fazer esse processo de retirada e Retorno dos quantificadores é o que nós estamos chamando aqui de particularização Universal e existencial e generalização Universal e existencial então no caso da particularização

Universal nós começamos dizendo que se uma propriedade válida para todos os elementos do domínio ela vai ser válida por um caso particular então por exemplo se P de x é o aluno X é alto e ter tudo é um aluno Então tudo é alto porque tá dizendo aqui que para todo x aluno ele é alto Então esse T ele pode ser como Eu mencionei o Túlio um elemento constante desse domínio ou pode ser uma variável só que aí temos que considerar algumas restrições por exemplo se ter formou uma variável ela não deve estar no escopo

de um quantificador para ter eu não vou poder usar como uma variável por um caso específico uma variável que já está sendo quantificada anteriormente bom começando com o caso simples todos os Homens São Mortais Sócrates é humano portanto Sócrates é mortal como vimos na última aula vamos representar isso aqui com predicados no caso MX é mortal hdx é humano e s para identificar o Sócrates dentro desse domínio bom todos os Homens São Mortais então para todo x se ele é homem então ele é mortal então é a maneira da gente interpretar isso aqui representar essa

esse argumento conforme já vimos na última aula ponto e Sócrates é humano então aqui particularizamos essa propriedade para Sócrates portanto Sócrates é mortal agora que representamos o argumento usando lógica de predicados vamos deduzir bom a minha hipótese nesse caso vai ser para todo x h x implica em MX e HS ocorre Beleza o que eu vou fazer retirar usar na nossa estratégia Nossa abordagem geral retirar o quantificador Universal então eu particularizo se ela é válida para todo mundo ela vai ser válida por Sócrates e eu escolhi o software justamente porque eu já tenho uma propriedade

relacionada a ele se isso aqui é válido para todo mundo então vai ser Válido por Sócrates através da particularização Universal e agora eu aplico modo disponíveis na linha dois e três deduzindo que Sócrates é mortal é mortal certo na linha 4 bom dessa forma nós vimos um caso aqui onde não tinha nenhuma restrição a ser observada agora se ter for uma variável ele não deve estar no escopo de um quantificador para ter por exemplo um exemplo aqui de uso incorreto seria nós temos aqui para todos x existe o x top P XY ocorre beleza para

todo x eu quero particularizar aí eu vou e particularizo para o y só que o y já tá sendo quantificado aqui então essa particularização Universal ela tá incorreta nesse um exemplo mais palpável disso se pxy fosse x menor que Y bom para todo x existe um Y tal que pxy ocorre isso é verdade mas se nesse processo de dedução eu tentasse inferir isso por exemplo usando constantes ou usando variáveis Ok deixando claro que essas variáveis estão seguindo isso aqui então eu tô considerando todo B é maior que a por exemplo a mais um agora se

eu particularizo por um Y que é um Y que já tá sendo usado uma variável livre que já tá sendo usado em outro modificador eu caio numa situação como essa que vai ser falsa na particularização existencial eu tenho que se existe a propriedade é válida para pelo menos algum elemento esse elemento é a por exemplo eu posso dizer que ele é o elemento A então a é uma variável ou um símbolo constante Qual que é a restrição deve ser a primeira regra a usar então em geral aqui o que se diz é o seguinte quando

a gente vai aplicar a particularização existencial numa demonstração o ideal é que ela seja feita primeiro então que nem aqui eu tenho duas hipóteses um envolvendo quantificador Universal e outro envolvendo um quantificadores existencial eu vou particularizar para esse aqui primeiro para evitar problemas na frente por exemplo se essa propriedade aqui existe o y que atende essa propriedade e eu falar que esse Y é o a que é levada para a eu sei que agora eu posso por exemplo afirmar que se para todo x essa propriedade válida ela vai ser válida para o ar que eu

particularizei aqui então eu aplico a particularização universal para essa mesma constante e agora cair um esquema de lógica entre aspas e proposicional no sentido que agora eu tô trabalhando com algo definido posso aplicar modos pôneis deduzir o que de a e pronto tenho a minha a dedução final na generalização Universal eu aqui eu tenho que tomar mais cuidado no sentido de que eu vou de um caso particular falar que é válido para todo mundo para isso então eu vou ter que ter restrições tomar cuidado com restrições relacionadas ao predicado Então nesse caso por exemplo não

pode ter sido não pode ter sido deduzida de hipóteses e onde X é uma variável livre e não pode ter sido deduzida via equivalência de uma fórmula bem formular Não desista também é uma variável Então eu tenho que dar uma muito cuidado na generalização a partir de uma variável Livre começar por um caso onde vai ser válido eu tenho aqui essa argumento eu separo hipótese hipótese certo particularizou a linha usa particularização Universal na linha 1 ok uso na linha 2 tranquilo aplica o modsponentes na linha 3 e 4 e agora Observe eu posso generalizar para

o pediatra porque porque esse esse quediar o uso desse q de a ele não tá sendo feito a partir de variáveis Livres o x aqui tá quantificado para o x aqui nessa relação de implicação tá quantificado quando eu obtive o pediaque o pediar a mesma coisa tá quantificado não são variáveis que estão livres Então nesse contexto eu posso retomar generalização Universal adicionar generalização Universal aqui no PX bom eu não vou poder fazer isso se o x for uma variável livre e qual que seria esse contexto eu tenho aqui a hipótese PX é verdadeira repare eu

tenho hipótese P de X é verdadeira onde x eu não tô dizendo que X é o João é uma constante X é uma variável livre eu não quantifiquei essa variável como é que se eu não quantifiquei essa variável como é que eu posso afirmar que ela vai valer essa propriedade vai valer para qualquer tipo de x Então você está incorreto tá um outro exemplo aqui né onde Eu Não Posso deduzir e equivalência a partir de uma fórmula bem informada no X é variável livre então aqui nesse caso a gente tem essa propriedade que x y

e observem que o que que eu faço aqui eu tenho eu vou partir da linha 1 eu aplico a particularização Universal E aí eu tenho aqui o x Mas eu deixei o x não como uma constante uma variável livre eu retirei o quantificador tudo bem só que agora o que que eu faço eu pego o meu existe Y substitui por uma constante A então eu tô dizendo agora que esse x variável ali variável livre está se relacionando com esse a caso particular de quando existe um livro Beleza agora eu vou dizer que esse x se

relaciona com o a Qualquer que seja esse x isso nem sempre vai ser verdadeiro tá porque o que diz a foi obtida via particularização existencial no passo 2 onde x era uma variável livre aqui tá nesse caso o que que acontece Vamos tentar dar um exemplo mais claro eu tenho aqui um existe Y que x y supor que seja x + y = 0 é verdadeiro eu sei que isso aqui vai ser válido para um X que seja igual a menos y agora quando eu particularizo para a isso só passa a valer para x igual

a menos a E aí como que desse ponto dessa particularização com x variável livre eu vou agora generalizar que para todo x isso vai valer Isso só vai valer para x igual a menos a tá bom e a generalização existencial a generalização existencial eu tenho que ela já é mais leve digamos assim de p de x ou P de a de um X uma variável livre ou pedia a um valor constante Eu Posso deduzir o que existe pelo menos um X que seja x livre mas tem pelo menos um caso para esse x que ele

ocorre que PX ocorre beleza Qual seria a restrição nesse caso para ir de pa para ir de pa no caso da Constante para existe x não pode aparecer em PA ou seja Considerando o pa aqui que o pa pode estar representando um predicado que não é só um na área binário Então nesse caso vamos ilustrar como exemplo mais simples aqui ó eu tenho que para todo x p x implica em existe um XP x meio Óbvio Mas vamos justificar isso a minha hipótese para todo x existe particular isso particularização Universal com x variável livre aqui

no caso só que tudo bem Tem uma variável livre eu posso agora dizer que existe pelo menos Justiça ao que precisa corre sem problema agora o caso que não satisfaz uma das restrições eu tenho aqui um predicado binário agora a y o y é uma variável Y variável livre e o ar é uma constante então eu vou e digo que existe um Y relacionada a esse agora já que o a ocorre Então existe um Y tal que isso aqui ocorre não né porque o meu Y ele já aparecia aqui na propriedade já parecia na propriedade

Então dessa forma eu caí de novo naquele caso se eu tenho um pxy X se for pedir y zero oky verdadeiro mas se for pedir Y já é falso certo Bom agora eu vou apresentar uma série de exemplos aplicando as regras começar por alguns exemplos de uso incorreto Por exemplo você pode querer aplicar Como Eu mencionei né retirar o quantificadores existencial dessa forma o que não estaria Ok por quê Porque a gente está tirando o fato da propriedade de existir um X para propriedade b e existe um X para propriedade que não quer dizer que

seu particularizo para o p Eu também tô particularizando porque nesse caso porque eu tenho que existe um a que satisfaz PX beleza mas não necessariamente o mesmo ar que satisfaz a propriedade que Então nesse caso o ideal aqui era ter um P.A e PB porque não necessariamente p e que vão ser satisfeitas para o mesmo objeto elemento a desse domínio tá então o escopo do primeiro computador existencial não pode ser estendido ao resto da Fórmula bem formulada outro exemplo aqui é por exemplo Eu mencionei vamos retirar então o quantificadores existencial primeiro sempre que possível porém

aqui nesse caso ele tá dentro do escopo desse para todo x existe um Y tal que XY ocorre então eu não posso primeiro particularizar para o existencial nesse caso então quantificadores essencial no Passo 1 não está à frente ele está dentro de um contexto desse para todo X então isso aqui também não tá correto bom agora para a gente aplicar um pouquinho as regras observem que eu vou um exemplo bem simples aqui eu tenho essa hipótese e vou agora destrinchar aqui separando os codificadores então eu começo particularizando o PX PX que nesse caso vai ficar

que a nesse caso válido porque o para todo x se refere PX e que X então se existe um a se existe se vale para todo x vai existir para um a PPA e que a porque aqui eu tô para todo se refere essas duas essas duas propriedades simultaneamente com isso eu posso agora aplicar simplificação e deduzir que pa se isso aqui é verdadeiro p a é verdadeiro que a é verdadeiro dessa forma agora eu posso retornar com quantificador é universal então eu posso generalizar usar generalização Universal já que o ar não foi deduzido a

partir de uma variável livre então eu posso generalizar para o p posso generalizar porque e compor através de uma conjunção a partir da linha 5 e 6 um outro exemplo aqui eu tenho S hipótese existe x tal qrx ocorre essa segunda hipótese que na verdade é uma negação de tudo que tá aqui dentro do existe x tal que RX e SX ocorre eu tô negando isso Observe que A negação se aplica tudo nesse caso Então a primeira coisa que eu faço é aplicar aquele equivalência que nós vimos na última aula de negar uma expressão Em

lógica de predicado onde nesse caso nós negamos o quantificador que sendo existencial passa a ser Universal e o predicado relacionado como aparece aqui na linha 3 dessa forma agora eu posso começar a remover os quantificadores eu começo pela linha 1 fazendo nesse caso né eu tenho uma existencial e um Universal eu começo pela existencial particularizando para a depois eu particularizo para o Universal usando esse mesmo a sendo que aqui agora eu posso por exemplo aplicar a lei de Morgan na linha 5 e em seguida a regra a equivalência condicional então eu tenho que isso aqui

eu nego primeiro termo troco pela implicação mantém o segundo termo agora eu posso aplicar modos phones na linha 4 e 7 deduzindo s a negado e se ocorre Não Há tal que essa negada é verdadeira eu vou poder dizer que existe um X tal que SX negado ocorre nesse caso também não estou violando nenhuma das restrições relacionadas não temos aqui contexto de nenhuma variável livre por exemplo bom dessa forma todos os conceitos exemplos apresentados Aqui foram baseados no que é descrito na sessão 1.4 do material básico Eu recomendo que vocês leiam Espero que tenham entendido

e nos encontramos na próxima aula muito obrigado [Música]