Lógica de predicados: Regra de dedução e quantificadores

Texto original

O texto original pode conter falhas de gramática ou de concordância, isso ocorre porque ele foi obtido por um processo de extração de texto automático.

Texto extraído do video Fundamentos Matemáticos para Computação - Lógica de Predicados

Olá,<|pt|> a Luanas e Amunos do Conselho Fundamentos Matemáticos para a Computação.
Nesta video-áulio, eu vou falar da lógica de predicaros.
Começá apresentando regros de dedução, considerando a particularização universal e a particularização existencial, depois apresentar a generação universal e existencial.
Por último, eu vou instrar a uso dessas regras através de exemplos.
Bom, diferente da lógica proposicional que podíamos provar a validade de um argumento usando, por exemplo, uma tabela de idade, na lógica de predicados nós utilizamos um sistema de forma ou um sistema de rebre de dedução para partir dessas hipóteses e chegar a conclusão desejada.
Para isso, o tassistema deve ser correto no sentido de que apenas há com menos valedos vão ser demonstrávios, e as hipóteses verdadeiras dentro de um domínio de interpretação vão levar a aplicação das regras de dedução a conclusão 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 vale do que deve ser demonstrado.
Além disso, ele busca ser tratável no sentido de que conseguimos realizar até as deduções no conjunto aplicando o convinto de regras.
As regras de equivalência e as regras de diferença que vêm no jovem na lógica proposicional ainda vão fazer parte desse sistema de lógica de forma ou de dedução na lógica de predicados.
Então, por exemplo, aqui nós temos esse argumento na lógica de predicados onde podemos identificar aqui essa hipóteses e essa aqui.
Então temos duas hipóteses.
Se observarmos, é sendo essa hipóteses verdadeira e essa implicação aqui também verdadeira.
Esse antecedente válido nos leva a inferir que esse consequente aqui também é válido, que é a regra de nossos póteses que vêm sendo aplicada na linha 1 e 2.
Mas a abordagem geral para se provar algo em lógica de predicados é tentar trazer dessa lógica de predicado para o esquema de lógica proposicional para as situações particulares.
Então é retirar os codificadores e manipulando.
A gente faz isso retirando os codificadores e manipulando as formas bem formados sem esses codificadores.
Depois, a gente retorna com eles e dependendo da conclusão que a gente quer chegar.
Para isso, nós vamos fazer esse processo de retirar, de retorno dos codificadores.
Nós estamos chamando de partícula deização universal e existencial e generalização universal e existencial.
Então, no caso da partícula deização universal, nós começamos dizendo que, se uma propriedade válida para todos os elementos do domínio, ela vai se revar e dá por um caso particular.
Então, por exemplo, se pdx é o aluno x é alto e t é um aluno, então, o t h é alto.
Porque está dizendo aqui que para todo x, o aluno é alto.
Então, este t pode ser, como eu mencionei o t h, um elemento constante desse domínio, ou pode ser uma variável.
Só que aí tem de que considerar algumas restrições.
Por exemplo, se t for uma variável, ela não deve estar no escopo de um pontificador 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 um 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, o mxx é mortal, hxx é humano.
E esse para eventificar o sócrates 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 de interpretar isso aqui, representar esse argumento, como, como já vimos na última aula.
Ponto e sócrates é humano.
Então, aqui, particularizamos essa propriedade para sócrates.
Portanto, sócrates é mortal.
Agora, aqui, representamos o argumento usando lógica de predicados, vamos deduzir.
Bom, a minha hipótese, nesse caso, vai ser para todo x, hx, impliquim, mx, e hx ocorre.
Beleza.
O que eu vou fazer? Retirar, usando a 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 para o sócrates.
E eu escolhi o sócrates justamente, porque eu já tenho uma propriedade relacionada a ele.
Se isso é válido para todo mundo, então, vai ser válido para o sócrates, através da particularização universal.
E agora eu aplico modos pónios na linha 2 e 3, 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 fome a 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 todo x, existe o x, tal que px, e o só ocorre.
Beleza, para todo x, eu quero particularizar.
Aí, eu vou ir particularizo para o íbselo.
Só que o íbselo já está sendo quantificado aqui.
Então, essa particularização universal, ela está incorreta.
Mesmo um exemplo mais palpável disso, se px, e o só, fosse x menor que íbselo, bom, para todo x, existe um íbselo, tal que px, e o só ocorre.
Isso é verdade.
Mas, 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 estou considerando todo b, maior que a, por exemplo, a mais 1.
Agora, se eu particularizo para um íbselo, que é um íbselo que já está sendo usado em uma variável livre, que já está sendo usado em outro quantificador, eu caio numa situação como essa, que vai ser falsa.
Bom, na particularização existencial, eu tenho que, se existe a propriedade avaliada, para pelo menos algum elemento, esse elemento é a, por exemplo, eu posso dizer que ele é a, pelo elemento a.
Então, há uma variável ou um símbolo constante.
Qualquer 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 2 hipóteses, não envolveram o quantificador universal e outro envolveram o quantificador essencial.
Eu vou particularizar para esse aqui primeiro, para evitar problemas na frente.
Por exemplo, se essa propriedade aqui é desistiuido, que atende essa propriedade, e eu falo que, se isso é o A, que é leválida 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 A que eu particularizei aqui.
Então, eu aplico a particularização universal para essa mesma constante, e agora reparei caí no esquema de lógica, tem trecho, por exemplo, proposicional, no sentido que agora eu estou trabalhando com algo definido, posso aplicar modos ponens, deduzir o que é de A.
E pronto, tenho a minha dedução final.
Na generalização universal, 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.
Nesse caso, por exemplo, não pode ter sido o praticoro, não pode ter sido deduzida de hipótese onde x é uma variável livre, e não pode ter sido deduzida via equivalência de uma fórmula performal onde x também é uma variável livre.
Então, eu tenho que estar uma muito cuidada 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? Particularizo universal, a linha usa a particularização universal na linha 1, ok, uso na linha 2, tranquilo, aplica modos ponens na linha 13 e 4, e agora observe, eu posso generalizar porque de A, porque, porque esse, esse que é de A, o uso desse que é de A, ele não está sendo feito a partir de variáveis livres.
O x aqui está quantificado para o x aqui, nessa relação de implicação, está quantificado quando eu obtive o que é de A aqui.
O pd A, a mesma coisa, está quantificado, não são variáveis que estão livres.
Então, nesse contexto, eu posso retomar a generalização universal.
A adicionar a generalização universal aqui no pd x.
Bom, eu não vou poder fazer isso se o x for uma variável livre.
E qual seria esse contexto? Eu tenho aqui hipótese, pd x é verdadeira, repare.
Eu tenho hipótese, pd x é verdadeira, onde x é não trizando que x é um João, é uma constante, o x é uma variável livre.
Eu não contifiquei essa variável.
Como é que se eu não contifiquei essa variável, como é que eu posso afirmar aquela variável na lei, essa propriedade, que vai valer para qualquer tipo x? Então, isso está incorreto.
Um outro exemplo aqui, onde eu não posso deduzir, que valência a partir de uma fórmula bem fórmula, não é uma variável livre.
Então, nesse caso, a gente tem essa propriedade que é de x, e observa que o que eu faço aqui? Eu tenho.
.
.
Eu vou.
.
.
parte 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 eu faço? Eu pego, o meu existe, só substituo para uma constante A.
Então, eu estou dizendo agora que esse x variável e.
.
.
Solão? Variável livre, está se relacionando com esse A, caso particular de quando existe um íbito.
Beleza.
Agora, eu vou dizer que esse x se relaciona com A, qualquer que seja esse x.
Isso nem sempre vai ser verdadeiro.
Porque o que x foi obtido à via, a particularização extensional no passo 2, onde x era uma variável livre aqui.
Nesse caso, o que que acontece? Vamos tentar dar um exemplo mais clara.
Eu tenho aqui um x, um x, e um suponho que seja x, mas y é igual a zero.
É 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.
E a generalização extensional.
A generalização extensional, eu tenho que ela já é mais leve, digamos assim, de px, o pd ádio, x é uma variável livre, o pd á é um valor constante, eu posso deduzir o que? Que existe pelo menos um x, seja, cix livre, as tempelulmendas um caso, para esse x que ele ocorre, que px ocorre.
Beleza.
Qual seria a restação nesse caso? Para ir de pA, para ir de pA, do caso da constante, para existe px, não pode aparecer em pA, ou seja, considerando o pA, o que o pA pode estar representando um predicado que não é só um nave, de nave, ter nário, em nero.
Então, nesse caso, vamos ilustrar, com um exemplo mais simples aqui, eu tenho que para todos os x px impliquem, existe um x px, meio óbvio, mas vamos justificar isso.
A minha hipótese para todo x, existe px, particulariz, 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 um x, tal que o px ocorre, sem problema.
Agora, o caso em que não satisfaz uma das restrições, eu tenho aqui um predicado binário agora, a y, o y é uma variável y, a variável livre, e o a é uma constante.
Então, eu vou e digo que existe um y, relacionado a esse a agora, já que o a ocorre, então, existe um y, não toque isso aqui ocorre, não.
Porque o meu y, ele já aparecia aqui na propriedade, já aparecia na propriedade.
Então, dessa forma, eu caio de novo naquele caso.
Se eu tenho px, o que é y, o que é x, se eu for px, zero, o que é y, o que é y, verdadeiro, mas se for px, o y já é falso, certo? Bom, agora eu vou apresentar uma série de exemplos, aplicando as regras, começaram por alguns exemplos de uso incorreto.
Por exemplo, você pode querer aplicar, como eu mencionei, retirar o continuador existencial dessa forma, porque não estaria ok, porque a gente está tirando o fato de dar propriedade, de existir o x para a propriedade p, e existir o x para a propriedade que não quer dizer que, se eu particularizo para o p, eu também estou particularizando por que nesse caso? Porque eu tenho que existir um x, satisfaz px, beleza, mas não necessariamente o mesmo x, satisfaz a propriedade que, então nesse caso, o ideal aqui era ter o pA e pB, porque não necessariamente a p, que é vão ser satisfeitas para um mesmo objeto, elemento a desse domínio, então, o escopo do primeiro continuador existencial não pode ser estendido ao resto da fórmula bem formulada.
Outro exemplo aqui, é, por exemplo, eu mencionei, e vamos retirar, então, o continuador existencial primeiro sempre que possível.
Porém, aqui nesse caso, ele está dentro do escopo, desse para todo x, existe um y toque, que x, y ocorre, então eu não posso primeiro particularizar para o ex-extencial nesse caso.
Então, o continuador extensional no passo 1 não está à frente, ele está dentro do contexto desse para todo x, então isso aqui também não está correto.
Bom, agora, para gente aplicar um pouquinho as regras, observem que eu vou, não exerPro bem simples aqui, eu tenho as repórtese, e vou agora distrinchar aqui separando os contificadores.
Então, eu começo particularizando o ProPX, que x, que nesse caso vai ficar P, aí que há nesse caso, o vale do porquê, o para todo x se refere, a Px é que x.
Então, se existe um y, se existe, se vale para todo x, vai existir para um a, P, P, A, e que há? Porque aqui eu estou, o para todo se refere a essas duas, essas duas, para treinar simultaneamente.
Com isso, eu posso agora aplicar, a simplificação, e deduzir que Px, isso aqui é verdadeiro, P, A é verdadeiro, que A é verdadeiro.
Dessa forma, agora, eu posso retornar com o contificador no universal.
Então, eu posso generalizar os a, generalização universal, já que o A não foi deduzido a partir de uma variável livre.
Então, eu posso generalizar ProP, posso generalizar ProQ, e compor a através de uma conjunção, a partir da linha 5 e 6.
Um outro exemplo aqui, porque tem S potas, e existe x, que é x.
Eu corre essa segunda hipótese, e que na verdade, é uma negação de tudo que está aqui dentro.
Do existe x, tal que Rx, e Sx, eu corre.
Eu estou negando isso, você sabe que a negação se aplica tudo.
Nesse caso, então, a primeira coisa que eu faço é aplicar aquela equivalência que nós vimos no ultimalo, de negar uma expressão inógica de predicado, onde, nesse caso, nós negamos o quantificador que sendo o existencial passa a seu universal e o predicado relacionado, como aparece aqui na linha 3.
Dessa forma, agora, eu posso começar a remover os quantificadores.
Então, eu começo pela linha 1 fazendo, nesse caso, eu tenho um existencial e o universal, eu começo pelo 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 demógar, na linha 5, e, em seguida, a equivalência condicional.
Então, eu tenho que isso aqui, porque nego primeiro termo, troca o opo e na implicação, mantém o segundo termo.
Agora, eu posso aplicar modos pôrninhos na linha 4 e 7, deduzindo esta ligada.
E se ocorre uma tal que esta ligada, é verdadeira, eu vou poder dizer que existe um x tal que esta x negada, concorra, nesse caso, também não estou violando nenhuma da gestrição relacionada, e não temos aqui contexto de nenhum novo alívio, por exemplo.
Bom, dessa forma, todos os conceitos, exemplos apresentados aqui, estão se foram baseados no que é descrito, na seção 1.
4 do material base, que eu recomendo que vocês leiam.
Espero que tenham entendido, e nos encontramos na próxima aula.
Muito obrigado.